Singleton coalition graph chains

被引:3
作者
Bakhshesh, Davood [1 ]
Henning, Michael A. [2 ]
Pradhan, Dinabandhu [3 ]
机构
[1] Univ Bojnord, Dept Comp Sci, Bojnord, Iran
[2] Univ Johannesburg, Dept Math & Appl Math, Auckland Pk, ZA-2006 Johannesburg, South Africa
[3] Indian Inst Technol ISM, Dept Math & Comp, Dhanbad, India
关键词
Coalition number; Domination number; Coalition partition; Coalition graphs;
D O I
10.1007/s40314-023-02588-0
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a graph with vertex set V and order n=|V|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n=|V|$$\end{document}. A coalition in G is a combination of two distinct sets, A subset of V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\subseteq V$$\end{document} and B subset of V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B\subseteq V$$\end{document}, which are disjoint and are not dominating sets of G, but their union A boolean OR B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\cup B$$\end{document} is a dominating set of G. A coalition partition of G is a partition P={S1, horizontal ellipsis ,Sk}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}=\{S_1,\ldots , S_k\}$$\end{document} of its vertex set V, where each set Si is an element of P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S_i\in {\mathcal {P}}$$\end{document} is either a dominating set of G with only one vertex, or it is not a dominating set but forms a coalition with some other set Sj is an element of P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S_j \in {\mathcal {P}}$$\end{document}. The coalition number C(G) is the maximum cardinality of a coalition partition of G. To represent a coalition partition P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}$$\end{document} of G, a coalition graph CG(G,P)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{CG}(G, {\mathcal {P}})$$\end{document} is created, where each vertex of the graph corresponds to a member of P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}$$\end{document} and two vertices are adjacent if and only if their corresponding sets form a coalition in G. A coalition partition P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}$$\end{document} of G is a singleton coalition partition if every set in P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}$$\end{document} consists of a single vertex. If a graph G has a singleton coalition partition, then G is referred to as a singleton-partition graph. A graph H is called a singleton coalition graph of a graph G if there exists a singleton coalition partition P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}$$\end{document} of G such that the coalition graph CG(G,P)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{CG}(G,{\mathcal {P}})$$\end{document} is isomorphic to H. A singleton coalition graph chain with an initial graph G1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} is defined as the sequence G1 -> G2 -> G3 -> MIDLINE HORIZONTAL ELLIPSIS\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1\rightarrow G_2\rightarrow G_3\rightarrow \cdots $$\end{document} where all graphs Gi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_i$$\end{document} are singleton-partition graphs, and CG(Gi,Gamma 1)=Gi+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{CG}(G_i, \varGamma _1)=G_{i+1}$$\end{document}, where Gamma 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varGamma _1$$\end{document} represents a singleton coalition partition of Gi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_i$$\end{document}. In this paper, we address two open problems posed by Haynes et al. We characterize all graphs G of order n and minimum degree delta(G)=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta (G)=2$$\end{document} such that C(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(G )= n$$\end{document}. Additionally, we investigate the singleton coalition graph chain starting with graphs G, where delta(G)<= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta (G)\le 2$$\end{document}.
引用
收藏
页数:22
相关论文
共 50 条
  • [41] The nonsplit domination number of a graph
    Kulli, VR
    Janakiram, B
    INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2000, 31 (04) : 441 - 447
  • [42] The Domination Number of a Random Graph
    Henning, Michael A.
    Yeo, Anders
    UTILITAS MATHEMATICA, 2014, 94 : 315 - 328
  • [43] The isolate bondage number of a graph
    R. Arul Ananthan
    S. Balamurugan
    Acta Mathematica Hungarica, 2025, 175 (2) : 395 - 410
  • [44] Graph products and integer domination
    John, Niluk
    Suen, Stephen
    DISCRETE MATHEMATICS, 2013, 313 (03) : 217 - 224
  • [45] A Note on the Bondage Number of a Graph
    李育强
    数学季刊, 1994, (04) : 1 - 4
  • [46] A new graph parameter and a construction of larger graph without increasing radio k-chromatic number
    Sarkar, Ushnish
    Adhikari, Avishek
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (04) : 1365 - 1377
  • [47] A new graph parameter and a construction of larger graph without increasing radio k-chromatic number
    Ushnish Sarkar
    Avishek Adhikari
    Journal of Combinatorial Optimization, 2017, 33 : 1365 - 1377
  • [48] DOMINATION NUMBERS OF m-CACTUS CHAINS
    Majstorovic, Snjezana
    Klobucar, Antoaneta
    Doslic, Tomislav
    ARS COMBINATORIA, 2016, 125 : 11 - 22
  • [49] Game domination subdivision number of a graph
    Favaron, O.
    Karami, H.
    Sheikholeslami, S. M.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 30 (01) : 109 - 119
  • [50] On Minimal and Vertex Minimal Dominating Graph
    Basavanagoud, B.
    Teredhahalli, I. M.
    JOURNAL OF INFORMATICS AND MATHEMATICAL SCIENCES, 2009, 1 (2-3): : 139 - 146