The minmin coalition number in graphs

被引:0
作者
Bakhshesh, Davood [1 ]
Henning, Michael A. [2 ]
机构
[1] Univ Bojnord, Dept Comp Sci, Bojnord, Iran
[2] Univ Johannesburg, Dept Math & Appl Math, ZA-2006 Auckland Pk, South Africa
基金
新加坡国家研究基金会; 芬兰科学院;
关键词
Coalition number; Domination number; Coalition partition; Dominating set;
D O I
10.1007/s00010-024-01045-5
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A set S of vertices in a graph G is a dominating set if every vertex of V(G)\S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(G) \setminus S$$\end{document} is adjacent to a vertex in S. A coalition in G consists of two disjoint sets of vertices X and Y of G, neither of which is a dominating set but whose union X boolean OR Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X \cup Y$$\end{document} is a dominating set of G. Such sets X and Y form a coalition in G. A coalition partition, abbreviated c-partition, in G is a partition X={X1, horizontal ellipsis ,Xk}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {X}} = \{X_1,\ldots ,X_k\}$$\end{document} of the vertex set V(G) of G such that for all i is an element of[k]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i \in [k]$$\end{document}, each set Xi is an element of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X_i \in {\mathcal {X}}$$\end{document} satisfies one of the following two conditions: (1) Xi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X_i$$\end{document} is a dominating set of G with a single vertex, or (2) Xi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X_i$$\end{document} forms a coalition with some other set Xj is an element of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X_j \in {\mathcal {X}}$$\end{document}. Let A={A1, horizontal ellipsis ,Ar}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {A}}} = \{A_1,\ldots ,A_r\}$$\end{document} and B={B1, horizontal ellipsis ,Bs}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {B}}}= \{B_1,\ldots , B_s\}$$\end{document} be two partitions of V(G). Partition B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {B}}}$$\end{document} is a refinement of partition A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {A}}}$$\end{document} if every set Bi is an element of B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B_i \in {{\mathcal {B}}} $$\end{document} is either equal to, or a proper subset of, some set Aj is an element of A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_j \in {{\mathcal {A}}}$$\end{document}. Further if A not equal B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {A}}} \ne {{\mathcal {B}}}$$\end{document}, then B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {B}}}$$\end{document} is a proper refinement of A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {A}}}$$\end{document}. Partition A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {A}}}$$\end{document} is a minimal c-partition if it is not a proper refinement of another c-partition. Haynes et al. [AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653-659] defined the minmin coalition number cmin(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_{\min }(G)$$\end{document} of G to equal the minimum order of a minimal c-partition of G. We show that 2 <= cmin(G)<= n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2 \le c_{\min }(G) \le n$$\end{document}, and we characterize graphs G of order n satisfying cmin(G)=n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_{\min }(G) = n$$\end{document}. A polynomial-time algorithm is given to determine if cmin(G)=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_{\min }(G)=2$$\end{document} for a given graph G. A necessary and sufficient condition for a graph G to satisfy cmin(G)>= 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_{\min }(G) \ge 3$$\end{document} is given, and a characterization of graphs G with minimum degree 2 and cmin(G)=4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_{\min }(G)= 4$$\end{document} is provided.
引用
收藏
页码:223 / 236
页数:14
相关论文
共 9 条
[1]   On the Coalition Number of Trees [J].
Bakhshesh, Davood ;
Henning, Michael A. ;
Pradhan, Dinabandhu .
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2023, 46 (03)
[2]  
Haynes T.W., IN PRESS
[3]  
Haynes T.W., 2022, Domination in Graphs: Core Concepts
[4]  
Haynes T. W., 1998, Fundamentals of Domination in Graphs, V208
[5]  
Haynes T.W., 2021, Structures of Domination in Graphs
[6]   Coalition graphs [J].
Haynes, Teresa W. ;
Hedetniemi, Jason T. ;
Hedetniemi, Stephen T. ;
McRae, Alice A. ;
Mohan, Raghuveer .
COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2023, 8 (02) :423-430
[7]  
Haynes TW, 2021, AUSTRALAS J COMB, V80, P442
[8]   Introduction to coalitions in graphs [J].
Haynes, Teresa W. ;
Hedetniemi, Jason T. ;
Hedetniemi, Stephen T. ;
McRae, Alice A. ;
Mohan, Raghuveer .
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (02) :653-659
[9]  
Henning M.A., 2013, Springer Monographs in Mathematics, DOI 10.1007/978-1-4614-6525-6