Dominating subgraphs in graphs with some forbidden structures
type: Item
instance of: scholarly article
title: Dominating subgraphs in graphs with some forbidden structures
zbMATH Open document ID: 0812.05052
DOI: 10.1016/0012-365X(93)E0111-G
published in: Discrete Mathematics
publication date: 1995-02-01T00:00:00Z
review text: Let \(G= G(V,E)\) be a simple finite graph without isolated vertices, \(P_ i\) a path with \(i\) vertices, and \(C_ i\) a cycle with \(i\) vertices. A set \(D\subseteq V(G)\) is a dominating set of \(G\) if, for any vertex \(v\) in \(V(G)\) but not in \(D\), there is a vertex \(u\) in \(D\) such that \(uv\) is an edge. \(D\) is said to dominate \(G\). A subgraph \(H\) of \(G\) is a dominating subgraph of \(G\) if \(V(H)\) dominates \(G\). \(G\) is said to be \(H\)-free if \(G\) has no induced subgraph which is isomorphic to \(H\). In the literature, for several classes of graphs \(\psi\), the classes \(G(\psi)\) of graphs with the property that all connected induced subgraphs of \(G\in G(\psi)\) have a dominating induced subgraph in \(\psi\), were characterized by so-called forbidden structures. In the present paper, the authors prove statements for the class of triangle-free graphs \(G\) in analogy to the Baćso-Tuza theorem, namely: (1) A graph \(G\) is both \(P_ 6\)-free and \(C_ 6\)-free iff every connected induced subgraph of \(G\) has a dominating complete bipartite subgraph (Theorem 1); and in a much stronger form: (2) \(G\) is \(P_ 6\)-free iff every connected induced subgraph of \(G\) has a dominating complete bipartite subgraph or a dominating induced \(C_ 6\) (Theorem 2). In the case where the graph \(G\) may contain triangles, the results are the following ones: (3) If \(G\) is a connected, \(P_ 6\)-free and \(C_ 6\)-free graph, then it has a dominating subgraph \(H\) which contains a dominating edge (Theorem 3); (4) A connected graph \(G\) is \(P_ 6\)-free iff each connected induced subgraph has a dominating clique or a dominating induced \(C_ 5\) (Theorem 4). Using a known theorem, from these results follows that a triangle-free graph is 3-colourable if every connected induced subgraph has an induced dominating bipartite subgraph.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 716455
zbMATH Keywords: dominating set
zbMATH Keywords: dominating subgraph
zbMATH Keywords: forbidden structures
author: Jiping Liu
author: Huishan Zhou
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: A characterization of graphs without long induced paths
cites work: Dominating cliques in \(P_ 5\)-free graphs
cites work: Q4227911
cites work: The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
cites work: Dominating cliques in graphs
cites work: On the existence of two non-neighboring subgraphs in a graph
cites work: Q3932997
cites work: The Comparability Graph of a Tree
description: scientific article; zbMATH DE number 716455