Open Access
Research Article
Fair dominating sets of paths
*Saeid AlikhaniCorresponding authoralikhani@yazd.ac.irDepartment of Mathematics Yazd UniversityDepartment of Mathematical Sciences Yazd UniversityYazd, 89195-741, Iran0000-0002-1801-203XView full profile → , Maryam Safazadehmsafazadeh92@gmail.comDepartment of Mathematics Yazd UniversityYazd, 89195-741, IranView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 09 Nov 2021
- Published Online:
- 05 Jul 2023
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-1141
- Pages:
- 855–864
Abstract
Let G = (V, E) be a simple graph. A dominating set of G is a subset D ⊆ V such that every vertex not in D is adjacent to at least one vertex in D. The cardinality of the smallest dominating set of G, denoted by g(G), is the domination number of G. For i ≥ 1, a i-fair dominating set (iFD-set) in G, is a dominating set S such that |N(v) ∩ D| = i for every vertex v ∈ V\D. A fair dominating set, in G is a iFD-set for some integer i ≥ 1. In this paper, we present the structure of fair dominating sets of a path and also we count the number of these sets.
Keywords
Subject Classifications
05C25
References
[1] Akbari, S., Alikhani, S., Peng, Y.H., Characterization of graphs using domination polynomial, Europ. J. Combin., 31 (2010) 1714-1724. [2] Alavi, Y., Malde, P.J., Schwenk, A.J., Erdös, The vertex independence sequence of a graph is not constrained, Congressus Numerantium 58 (1987) 15-23. [3] Alikhani, S., Akhbari, M.H., Eslahchi, C., Hasni, R., On the number of outer connected dominating sets of graphs, Utilitas Math. 91 (2013) 99-107. [4] Alikhani, S., Peng, Y.H., Introduction to domination polynomial of a graph, Ars Combin. 114 (2014) 257-266. [5] Alikhani, S., Safazadeh, M., On the number of fair dominating sets of graphs, submitted. Available at https://arxiv.org/abs/2107.10671. [6] Beaton,I., Brown, J.I., On the unimodality of domination polynomials, Available at https://arxiv.org/abs/2012.11813. [7] Brown, J.I., Tufts, J., On the roots of domination polynomials, Graphs Combin. 30, (2014) 527-547. [8] Caro, Y., Hansberg, A., Henning, M., Fair domination in graphs, Discrete Appl. Math. 312 (2012) 2905-2914. [9] Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (1998) Fundamentals of domination in graphs. Marcel Dekker, NewYork. [10] Heubach, S., Mansour, T., Compositions of n with parts in a set, Congressus Numerantium 168 (2004) 33-51. [11] Huh, J., Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, J. Amer. Math. Soc. 25 (2012) 907-927. [12] Kotek, T., Preen, J., Simon, F., Tittmann, P., Trinks, M., Recurrence relations and splitting formulas for the domination polynomial, Elec. J. Combin. 19(3) (2012) 27 pp. [13] Lau, G.C., Alikhani, S., More on the unimodality of domination polynomial of a graph, Discrete Math. Alg. Appl., in press. https://doi.org/10.1142/S179383092150138X. [14] Read, R.C., An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52-71.
Views: 171Downloads: 6Citations: 0
