Article in press
Authors:
Saeid Alikhani
Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran.
email: alikhani@yazd.ac.ir
Davood Bakhshesh
Department of Computer Science,
University of Bojnord, Bojnord, Iran
email: d.bakhshesh@ub.ac.ir
Elena V. V. Konstantinova
Sobolev Institute of Mathematics, Novosibirsk State University
email: e_konsta@math.nsc.ru
Title:
Connected coalitions in graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-02-26 , Revised: 2023-07-08 , Accepted: 2023-07-09 , Available online: 2023-07-27 , https://doi.org/10.7151/dmgt.2509
Abstract:
Let $G = (V,E)$ be a graph, and define a connected coalition as a pair of
disjoint vertex sets $U_{1}$ and $U_{2}$ such that $U_{1}\cup U_{2}$ forms a
connected dominating set, but neither $U_{1}$ nor $U_{2}$ individually forms a
connected dominating set. A connected coalition partition of $G$ is a partition
$\Phi=\{U_1, U_2,\dots, U_k\}$ of the vertices such that each set $U_i \in \Phi$
either consists of only a single vertex with degree $n-1$, or forms a connected
coalition with another set $U_j\in \Phi$ that is not a connected dominating set.
The connected coalition number $CC(G)$ is defined as the largest possible size
of a connected coalition partition for $G$.
The objective of this study is to initiate an examination into the notion of
connected coalitions in graphs and present essential findings. More precisely,
we provide a thorough characterization of all graphs possessing a connected
coalition partition. Moreover, we establish that, for any graph $G$ with order
$n$, a minimum degree of $1$, and no full vertex, the condition $CC(G)<n$ holds.
In addition, we prove that any tree $T$ achieves $CC(T)=2$. Lastly, we propose
two polynomial-time algorithms that determine whether a given connected graph
$G$ of order $n$ satisfies $CC(G)=n$ or $CC(G)=n-1$.
Keywords:
coalition, coalition partition, polynomial-time algorithm, corona product
References:
- S. Alikhani, D. Bakhshesh and H.R. Golmohammadi, Introduction to total coalitions in graphs.
arXiv: 2211.11590 - S. Alikhani, H. Golmohammadi and E.V. Konstantinova, Coalition of cubic graphs of order at most $10$, Commun. Comb. Optim, in press.
https://doi.org/10.22049/cco.2023.28328.1507 - S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of natural and fractional powers of graphs, Bull. Iranian Math. Soc. 43 (2017) 2471–2482.
- D. Bakhshesh, M.A. Henning and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46 (2023) 95.
https://doi.org/10.1007/s40840-023-01492-4 - E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247–261.
https://doi.org/10.1002/net.3230070305 - D.-Z. Du and P.-J. Wan, Connected Dominating Set: Theory and Applications (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-5242-3 - B.L. Hartnell and D.F. Rall, Connected domatic number in planar graphs, Czechoslovak Math. J. 51 (2001) 173–179.
https://doi.org/10.1023/A:1013770108453 - T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2020) 653–659.
https://doi.org/10.1080/09728600.2020.1832874 - T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Coalition graphs of paths, cycles and trees, Discuss. Math. Graph Theory, in press.
https://doi.org/10.7151/dmgt.2416 - T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Upper bounds on the coalition number, Australas. J. Combin. 80 (2021) 442–453.
- T.W. Haynes, S.T. Hedetniemi and M.A.Henning, Topics in Domination in Graphs (Dev. Math. 64 Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Boca Ratan, CRC Press, New York, 1998).
https://doi.org/10.1201/9781482246582 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Routledge, Inc., New York, 1998).
https://doi.org/10.1201/9781315141428 - E. Sampathkumar and H.B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979) 607–613.
- B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983) 145–147, http://dml.cz/dmlcz/136324.
- B. Zelinka, On domatic numbers of graphs, Math. Slovaca 31 (1981) 91–95, http://dml.cz/dmlcz/132763.
- B. Zelinka, Connected domatic number of a graph, Math. Slovaca 36 (1986) 387–392, http://dml.cz/dmlcz/136430.
Close