Premium
Dominating sets with small clique covering number
Author(s) -
Penrice Stephen G.
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199706)25:2<101::aid-jgt1>3.0.co;2-q
Subject(s) - combinatorics , mathematics , dominating set , vertex (graph theory) , discrete mathematics , simplex graph , graph , clique graph , induced subgraph , split graph , distance hereditary graph , clique , line graph , graph power , pathwidth
Motivated by earlier work on dominating cliques, we show that if a graph G is connected and contains no induced subgraph isomorphic to P 6 or H t (the graph obtained by subdividing each edge of K 1,t , t ≥ 3, by exactly one vertex), then G has a dominating set which induces a connected graph with clique covering number at most t − 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 101–105, 1997