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

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-656985

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.