TARU PUBLICATIONS
Journal of Information and Optimization Sciences cover

Journal of Information and Optimization Sciences

(Since 1980)
Hybrid ·Peer-reviewed·ISSN (Online): 2169-0103·ISSN (Print): 0252-2667

WoS  JIF 2026 : 0.4 (Q4)

Powered by:Powered by

Monthly Journal: Publishes theoretical and applied research on topics in information and optimization sciences.

Issues up to 2022 co-published with and available at:Taylor & Francis
submissions@tarupublications.com
Taru Online First Current IssueSpecial IssuesBrowse all Issues
Journal of Information and Optimization Sciences
Open Access Research Article

Fair dominating sets of paths

* ,

* Corresponding author · click or hover a name for details

pp. 855–864Vol. 44Issue 5July 2023DOI: 10.47974/JIOS-1141XML
Received:
09 Nov 2021
Published Online:
10 Oct 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

Composition of a numberFair dominating setPath

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: 211Downloads: 79Citations: 0