$H$-product and $H$-threshold graphs - Mathematics > CombinatoricsReportar como inadecuado




$H$-product and $H$-threshold graphs - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: This paper is the continuation of the research of the author and hiscolleagues of the {\it canonical} decomposition of graphs. The idea of thecanonical decomposition is to define the binary operation on the set of graphsand to represent the graph under study as a product of prime elements withrespect to this operation. We consider the graph together with the arbitrarypartition of its vertex set into $n$ subsets $n$-partitioned graph. On theset of $n$-partitioned graphs distinguished up to isomorphism we consider thebinary algebraic operation $\circ H$ $H$-product of graphs, determined by thedigraph $H$. It is proved, that every operation $\circ H$ defines the uniquefactorization as a product of prime factors. We define $H$-threshold graphs asgraphs, which could be represented as the product $\circ {H}$ of one-vertexfactors, and the threshold-width of the graph $G$ as the minimum size of $H$such, that $G$ is $H$-threshold. $H$-threshold graphs generalize the classes ofthreshold graphs and difference graphs and extend their properties. We show,that the threshold-width is defined for all graphs, and give thecharacterization of graphs with fixed threshold-width. We study in detail thegraphs with threshold-widths 1 and 2.



Autor: Pavel Skums

Fuente: https://arxiv.org/







Documentos relacionados