کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647515 | 1342356 | 2013 | 11 صفحه PDF | دانلود رایگان |

One method of graph decomposition is to define a binary operation on the set of graphs and to represent graphs as products of prime elements with respect to this operation. We consider a graph together with a partition of its vertex set into nn subsets (nn-partitioned graph). On the set of all isomorphism classes of nn-partitioned graphs we consider a binary algebraic operation ∘H∘H (HH-product of graphs), determined by a digraph HH. We prove that every operation ∘H∘H defines the unique factorization as a product of prime factors. We define HH-threshold graphs as graphs that can be represented as products of one-vertex factors under the operation ∘H∘H. Threshold-width of a graph GG is the minimum number of vertices in a digraph HH such that GG is an HH-threshold graph. In particular, threshold graphs and difference graphs are HH-threshold graphs for certain digraphs HH. Threshold-width is naturally related to clique-width and NLCNLC-width of graphs. Graphs with bounded threshold-width generalize threshold graphs and difference graphs and extend their properties. We characterize graphs with bounded threshold-width and study in detail graphs with threshold-width at most 22.
Journal: Discrete Mathematics - Volume 313, Issue 21, 6 November 2013, Pages 2390–2400