$H$-product and $H$-threshold graphs

Details $H$-product and $H$-threshold graphs $H$-product and $H$-threshold graphs

2010-11-22

arxiv.org/abs/1011.4726v2

Mathematics

Combinatorics

Scientific paper

This paper is the continuation of the research of the author and his colleagues of the {\it canonical} decomposition of graphs. The idea of the canonical decomposition is to define the binary operation on the set of graphs and to represent the graph under study as a product of prime elements with respect to this operation. We consider the graph together with the arbitrary partition of its vertex set into $n$ subsets ($n$-partitioned graph). On the set of $n$-partitioned graphs distinguished up to isomorphism we consider the binary algebraic operation $\circ_H$ ($H$-product of graphs), determined by the digraph $H$. It is proved, that every operation $\circ_H$ defines the unique factorization as a product of prime factors. We define $H$-threshold graphs as graphs, which could be represented as the product $\circ_{H}$ of one-vertex factors, 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 of threshold graphs and difference graphs and extend their properties. We show, that the threshold-width is defined for all graphs, and give the characterization of graphs with fixed threshold-width. We study in detail the graphs with threshold-widths 1 and 2.

Affiliated with

Also associated with

No associations

Rating

$H$-product and $H$-threshold graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with $H$-product and $H$-threshold graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $H$-product and $H$-threshold graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-656985