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 条
  • [21] On the trace graph of matrices
    Sivagami, M.
    Chelvam, T. Tamizh
    ACTA MATHEMATICA HUNGARICA, 2019, 158 (01) : 235 - 250
  • [22] INTERSECTION GRAPH OF A MODULE
    Yaraneri, Ergun
    JOURNAL OF ALGEBRA AND ITS APPLICATIONS, 2013, 12 (05)
  • [23] On a graph of monogenic semigroups
    K Ch Das
    Nihat Akgüneş
    A Sinan Çevik
    Journal of Inequalities and Applications, 2013
  • [24] Domsaturation number of a graph
    Arumugam, S
    Kala, R
    INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2002, 33 (11) : 1671 - 1676
  • [25] The bondage and connectivity of a graph
    Liu, HL
    Sun, L
    DISCRETE MATHEMATICS, 2003, 263 (1-3) : 289 - 293
  • [26] On the domination number of a graph
    Pruchnewski, A
    DISCRETE MATHEMATICS, 2002, 251 (1-3) : 129 - 136
  • [27] Bounds on the differential of a graph
    Basilio, Ludwin A.
    Bermudo, Sergio
    Sigarreta, Jose M.
    UTILITAS MATHEMATICA, 2017, 103 : 319 - 334
  • [28] On a graph of monogenic semigroups
    Das, Kinkar Ch.
    Akgunes, Nihat
    Cevik, A. Sinan
    JOURNAL OF INEQUALITIES AND APPLICATIONS, 2013,
  • [29] On the trace graph of matrices
    M. Sivagami
    T. Tamizh Chelvam
    Acta Mathematica Hungarica, 2019, 158 : 235 - 250
  • [30] The path graph of the amalgamated graph of C3 and Cn at an edge or at a vertex
    Hussein, Eman
    Al-Ezeh, Hasan
    Abu Ghneim, Omar
    ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2020, (43): : 492 - 502