The extended irregular domination problem

Document Type : Original paper

Authors

1 Dip. di Scienze Fisiche, Informatiche, Matematiche, Universitá degli Studi di Modena e Reggio Emilia, Via Campi 213/A, I-41125 Modena, Italy

2 DICATAM - Sez. Matematica, Universitá degli Studi di Brescia, Via Branze 43, I-25123 Brescia, Italy

Abstract

In this paper we introduce a new domination problem strongly related to the following one recently proposed by Broe, Chartrand and Zhang. One says that a vertex $v$ of a graph $\Gamma$ labeled with an integer $\ell$ dominates the vertices of $\Gamma$ having distance $\ell$ from $v$. An irregular dominating set of a given graph $\Gamma$ is a set $S$ of vertices of $\Gamma$, having distinct positive labels, whose elements dominate every vertex of $\Gamma$. Since it has been proven that no connected vertex transitive graph admits an irregular dominating set, here we introduce the concept of an \emph{extended} irregular dominating set, where we admit that precisely one vertex, labeled with 0, dominates itself. Then we present existence or non existence results of an extended irregular dominating set $S$ for several classes of graphs, focusing in particular on the case in which $S$ is as small as possible. We also propose two conjectures.   

Keywords

Main Subjects

References

[1] A. Ali, G. Chartrand, and P. Zhang, On irregular and antiregular domination in graphs, Electron. J. Math. 2 (2021), 26–36. https://doi.org/10.47443/ejm.2021.0032
[2] C. Berge, Sur le couplage maximum d’un graphe, C. R. Acad. Sci. Paris 247 (1958), 258–259.
[3] P. Broe, Irregular Orbital Domination in Graphs, Dissertations (2022), 3826.
[4] P. Broe, G. Chartrand, and P. Zhang, Irregular domination in trees, Electronic J. Math 1 (2021), 89–100. https://doi.org/10.47443/ejm.2021.0013
[5] P. Broe, G. Chartrand, and P. Zhang, Irregular orbital domination in graphs, Int. J. Comput. Math. Comput. Syst. Theory 7 (2022), no. 1, 68–79. https://doi.org/10.1080/23799927.2021.2014977
[6] G. Chartrand and P. Zhang, A chessboard problem and irregular domination, Bull. Inst. Combin. Appl. 98 (2023), 43–59.
[7] K. Chen, G. Ge, and L. Zhu, Starters and related codes, J. Statist. Plann. Inference 86 (2000), no. 2, 379–395. https://doi.org/10.1016/S0378-3758(99)00119-6
[8] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), no. 3, 247–261. 
https://doi.org/10.1002/net.3230070305
[9] J.H. Dinitz, Starters, Handbook of Combinatorial Designs (C.J. Colbourn and J.H. Dinitz, eds.), Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, 2006, pp. 622–628.
[10] J.H. Dinitz and D.R. Stinson (eds.), Contemporary design theory: A collection of surveys, 1992.
[11] R.M. Falcón, private communication.
[12] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer, 2023.
[13] J.D. Horton, Orthogonal starters in finite abelian groups, Discrete Math. 79 (1990), no. 3, 265–278. https://doi.org/10.1016/0012-365X(90)90335-F
[14] Y.S. Liaw, More $\mathbb Z$-cyclic room squares, Ars Combin. 52 (1999), 228–238.
[15] S. Lins and P.J. Schellenberg, The existence of skew strong starters in $\mathbb Z_{16^{t^2}+1}$: a simpler proof, Ars Combin. 11 (1981), 123–129.
[16] C. Mays and P. Zhang, Irregular domination graphs, Contrib. Math. 6 (2022), 5–14. https://doi.org/10.47443/cm.2022.033
[17] C. Mays and P. Zhang, Irregular domination trees and forests, Discrete Math. Lett. 11 (2023), 31–37. https://doi.org/10.47443/dml.2022.119
[18] R.C. Mullin and E. Nemeth, An existence theorem for Room squares, Canad. Math. Bull. 12 (1969), no. 4, 493–497. https://doi.org/10.4153/CMB-1969-063-6
[19] O. Ore, Theory of Graphs, vol. 38, American Mathematical Society Colloquium Publications, 1962.
[20] N. Shalaby, Skolem and Langford sequences, Handbook of Combinatorial Designs (C.J. Colbourn and J.H. Dinitz, eds.), Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, 2007, pp. 612–616.
[21] D.R. Stinson, Some new results on skew frame starters in cyclic groups, Discrete Math. 346 (2023), no. 8, Article ID: 113476. https://doi.org/10.1016/j.disc.2023.113476
[22] D.R. Stinson, Orthogonal and strong frame starters: Revisited, Fields Institute Communications 86 (2024), 393–407.
Communications in Combinatorics and Optimization
Volume 11, Issue 3
September 2026
Pages 717-737

Files

Share

How to cite

Statistics