Article ID Journal Published Year Pages File Type
4647515 Discrete Mathematics 2013 11 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,