No Detail Found!

Excellent graphs with respect to domination: subgraphs induced by minimum dominating sets

Author(s)
Vladimir Samodivkin Department of Mathematics, University of Architecture, Civil Engineering and Geodesy,Sofia 1164,Bulgaria
Abstract
A graph G = (V (G); E(G)) is -excellent if V (G) is the union of all -sets of G, where stands for the domination number of G and a -set is a dominating set of cardinality . Let I be a set of all mutually nonisomorphic graphs and let ; 6= H ( I. In this paper, the study of the H- -excellent graphs is initiated. A graph G is H- -excellent if the following conditions hold: (i) for every H 2 H and for each x 2 V (G) there exists an induced subgraph Hx of G such that H and Hx are isomorphic, x 2 V (Hx) and V (Hx) is a subset of some -set of G, and (ii) the vertex set of every induced subgraph H of G, which is isomorphic to some element of H, is a subset of some -set of G. We consider some well-known graphs, including cycles, trees and some cartesian products of two graphs, and for every considered graph we describe its largest set H ( I for which the graph is H- -excellent. Results on -excellent regular graphs and on a generalized lexicographic product of graphs are presented. Several open problems and questions are also posed.
Publication Details
Page(s) 12-19
Published Journal: Discrete Mathematics Letters, Volume: 5, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords
excellent graph, graph product, domination number
References
Berge C.,Saito C. .1981 .Some common properties for regularizable graphs, edge-critical graphs, and b-graphs. Graph Theory and Algorithms, 108 : 108-123.
Brigham R. C.,Chinn P. Z.,Dutton R. D. .1988 .Vertex domination-critical graphs. Networks, 18 : 173-179.
Burton T.,Sumner D. P. .2007 .-Excellent, critically dominated, end-dominated, and dot-critical trees are equivalent. , 307 : 683-693.
Dean N.,Zito J. .1994 .Well-covered graphs and extendability. , 126 : 67-80.
El-Zahar M.,Pareek C. M. .1991 .Domination number of products of graphs. Ars Combin, 31 : 223-227.
Fricke G.,Haynes T.,Hedetniemi S.,Hedetniemi S.,Laskar R. .2002 .Excellent trees. Bull. Inst. Combin. Appl, 34 : 27-38.
Grobler P. J. P. .1998 .. PhD thesis, : .
Haynes T. W.,Hedetniemi S. T.,Slater P. J. .1998 .. , : .
Haynes T. W.,Henning M. A. .2002 .A characterization of i-excellent trees. Discrete Math, 248 : 69-77.
Henning M. A. .2003 .Total domination excellent trees. Discrete Math, 263 : 93-104.
Jayaram S. R. .1997 .Minimal dominating sets of cardinality two in graphs. Indian J. Pure Appl, 28 : 43-46.
Meringer M. .1999 .Fast generation of regular graphs and construction of cages. J. Graph Theory, 30 : 137-146.
Meringer M. . .. , : .
C. M. Mynhardt H. C.,Stwart H. C. .2005 .Excellent trees. , 67 : 255-267.
M. D. Plummer .1970 .Some covering concepts in graphs. J. Combin. Theory, 8 : 91-98.
Reed B. .1996 .Paths, stars and the number three. Combin. Probab. Comput, 5 : 267-276.
Samodivkin V. . .. God. Univ. Arkhit. Stroit. Geod. Sofiya Svitk II Mat. Mekh, 39(1996-1997) : 111-135.
Samodivkin V. . .Roman domination excellent graphs: trees. Commun. Comb. Optim, 3(2018) : 1-24.
Sohn Y.,Yuan X. .2009 .Domination in graphs of minimum degree four. J. Korean Math. Soc, 46 : 759-773.
Sridharan N.,Yamuna M. .2007 .Very excellent graphs and rigid very excellent graphs. AKCE J. Graphs. Combin, 4 : 211-221.
Sumner D. P.,Blitch P. .1983 .. J. Combin. Theory Ser. B, 34 : 65-76.
H. M. Xing L.,Sun X. G.,Chen X. G. .2006 .Domination in graphs of minimum degree five. Graphs Combin, 22 : 127-143.
Yamuna M.,Sridharan N. .2010 .. Int. J. Engin. Sci. Adv. Comput. Bio-Technol, 1 : 129-136.
0

Citations

0

Downloads

13

Views