Vertex sequences in graphs

Teresa W. Haynes; Stephen T. Hedetniemi

doi:10.47443/dml.2021.s103

Author(s)

Teresa W. Haynes Department of Mathematics and Statistics, East Tennessee State University, Johnson, TN 37614–0002, USA; Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park 2006, South Africa

Stephen T. Hedetniemi School of Computing, Clemson University, Clemson, SC 29634, USA

Abstract

We consider a variety of types of vertex sequences, which are defined in terms of a requirement that the next vertex in the sequence must meet. For example, let S = (v1; v2; : : : ; vk) be a sequence of distinct vertices in a graph G such that every vertex vi in S dominates at least one vertex in V that is not dominated by any of the vertices preceding it in the sequence S. Such a sequence of maximal length is called a dominating sequence since the set fv1; v2; : : : ; vkg must be a dominating set of G. In this paper we survey the literature on dominating and other related sequences, and propose for future study several new types of vertex sequences, which suggest the beginning of a theory of vertex sequences in graphs.

Publication Details

Page(s) 19-31

DOI 10.47443/dml.2021.s103

Published Journal: Discrete Mathematics Letters, Volume: 6, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords

vertex cover, domination, irredundance, grid graphs, dominating sequences, zero forcing number, total domination, vertex sequences, connected domination

References

. .4. a signed domination sequence S = (v1; v2; : : : ; vk) is a vertex sequence having the property that for every vi. , : .

Aazami A. .2008 .Hardness Results and Approximation Algorithms for Some Problems on Graphs. PhD Thesis, : .

Aazami A. .2010 .Domination in graphs with bounded propagation: algorithms, formulations and hardness results. J. Comb. Optim, 19 : 429-456.

Aazami A.,Stilp M. D. .2007 .Approximation algorithms and hardness for domination with propagation. In: Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Lecture Notes in Comput. Sci. 4627, : 1-15.

Aazami A.,Stilp K. .2009 .Approximation algorithms and hardness for domination with propagation. SIAM J. Discrete Math, 23 : 1382-1399.

Arumugam S.,Hedetniemi S. T.,Hedetniemi S. M.,Sathikala L.,S. Sudha, L. .2015 .The covering chain of a graph, Util. , 98 : 183-196.

Baldwin T. L.,Mili L.,Boisen M. B.,Adapa R. .1993 .Power system observability with minimal phasor measurement placement. IEEE Trans. Power Syst, 8 : 707-715.

Barioli F.,Barrett W.,Butler S.,Cioaba S. M.,Cvetkovic D.,Fallat S. M.,Godsil C.,Haemers W.,Hogben L.,Mikkelson R.,Narayan S.,Pryporova O.,So W.,Stevanovic D.,Vander Meulen K.,Wangsness A. .2008 .Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl, 428 : 1628-1648.

Bresˇar B.,Tuza Z.,Vizer M. . .Dominating sequences in grid-like and toroidal graphs. Electron. J. Combin, 23(2016) : 34.

Bresˇar B.,Tuza Z.,Vizer M. .2017 .Grundy dominating sequences and zero forcing sets. Discrete Optim, 26 : 66-77.

Bresˇar B. .2016 .Dominating sequences under atomic changes with applications in Sierpin´ ski and interval graphs. Appl. Anal. Discrete Math, 10 : 518-531.

Bresˇar B.,M. Milanicˇ D. F.,Rall R.,Rizzi R. .2014 .. , 336 : 22-36.

Bresˇar B.,Henning M. A.,Rall D. F. .2016 .Total dominating sequences in graphs. , 339 : 1665-1676.

Bresˇar B.,Rall D. F. .2010 .Domination game and an imagination strategy. SIAM J. Discrete Math, 24 : 979-991.

Bresˇar B.,Torres P. .2018 .Total dominating sequences in trees, split graphs, and under modular decomposition. Discrete Optim, 28 : 16-30.

Broere I.,Domke G. S. .2006 .The induced path number of the Cartesian product of some graphs, Australas. , 36 : 3-12.

Brueni D. J. .1993 .Minimal PMU Placement for Graph Observability: A Decomposition Approach. , : .

Brueni D. J.,Heath L. S. .2005 .The PMU placement problem. SIAM J. Discrete Math, 19 : 744-761.

Buckley F.,Harary F. .1988 .On longest induced paths in graphs, Chinese Quart. J. Math. 3, : 61-65.

Cockayne E. J.,Grobler P. J. P.,Hedetniemi S. T.,McRae A. A. .1997 .What makes an irredundant set maximal?. J. Combin. Math. Combin. Comput, 25 : 213-223.

Cockayne E. J.,Hattingh J. H.,Hedetniemi S. M.,Hedetniemi S. T.,McRae A. A. .1997 .Using maximality and minimality conditions to construct inequality chains. , 176 : 43-61.

Cockayne E. J.,Hedetniemi S. T.,Miller D. J. .1978 .Properties of hereditary hypergraphs and middle graphs. Canad. Math. Bull, 21 : 461-468.

Hattingh J. H.,Saleh O. A.,Van der Merwe L. C.,Walters L. C. .2013 .Nordhaus-Gaddum type results for the induced path number with relative complements in Km;n. J. Combin. Math. Combin. Comput, 85 : 365-377.

Haynes T. W.,Hedetniemi S. M.,Hedetniemi S. T.,Henning M. A. .2002 .Domination in graphs applied to electric power networks. SIAM J. Discrete Math, 15 : 519-529.

Haynes T. W.,Hedetniemi S. T.,Slater P. J. .1998 .. , : .

Henning M. A.,Rall D. F. .2015 .Total version of the domination game. Graphs Combin, 31 : 1453-1462.

Ishizeki T.,Otachi Y.,Yamazaki K. .2008 .An improved algorithm for the longest induced path problem on k-chordal graphs. Discrete Appl. Math, 156 : 3057-3059.

J. C.-H. Lin .2019 .Zero forcing number, Grundy domination number, and their variants. Linear Algebra Appl, 563 : 240-254.