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 条
  • [1] Singleton coalition graph chains
    Davood Bakhshesh
    Michael A. Henning
    Dinabandhu Pradhan
    Computational and Applied Mathematics, 2024, 43
  • [2] On the Coalition Number of Trees
    Davood Bakhshesh
    Michael A. Henning
    Dinabandhu Pradhan
    Bulletin of the Malaysian Mathematical Sciences Society, 2023, 46
  • [3] On the Coalition Number of Trees
    Bakhshesh, Davood
    Henning, Michael A.
    Pradhan, Dinabandhu
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2023, 46 (03)
  • [4] COMPLEMENTARY COALITION GRAPHS: CHARACTERIZATION AND ALGORITHM
    Bakhshesh, Davood
    Henning, Michael A.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024,
  • [5] The minmin coalition number in graphs
    Bakhshesh, Davood
    Henning, Michael A.
    AEQUATIONES MATHEMATICAE, 2025, 99 (01) : 223 - 236
  • [6] The minmin coalition number in graphsThe minmin coalition number in graphsD. Bakhshesh, M. A. Henning
    Davood Bakhshesh
    Michael A. Henning
    Aequationes mathematicae, 2025, 99 (1) : 223 - 236
  • [7] The shortest cycle having the maximal number of coalition graphs
    Dobrynin, Andrey A.
    Golmohammadi, Hamidreza
    DISCRETE MATHEMATICS LETTERS, 2024, 14 : 21 - 26
  • [8] EDGE DOMINATING GRAPH OF A GRAPH
    Basavanagoud, B.
    Hosamani, Sunilkumar M.
    TAMKANG JOURNAL OF MATHEMATICS, 2012, 43 (04): : 603 - 608
  • [9] ON CUBIC GRAPHS HAVING THE MAXIMUM COALITION NUMBER
    Dobrynin, A. A.
    Golmohammadi, H.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2024, 21 (01): : 363 - 369
  • [10] DOMINATION NUMBERS ON THE BOOLEAN FUNCTION GRAPH OF A GRAPH
    Janakiraman, T. N.
    Muthammai, S.
    Bhanumathi, M.
    MATHEMATICA BOHEMICA, 2005, 130 (02): : 135 - 151