Browse Items (7684 total)
Sort by:
-
Introduction to connecting coalitions
A connecting coalition in a graph G(V;E) consists of two disjoint vertex subsets V1 and V2 of V (G), where neither G[V1] nor G[V2] is a connected graph but G[V1 [V2] is a con- nected graph. A connecting coalition partition is a vertex partition ? = fV1; V2; : : : ; Vkg, and the maximum cardinality of all possible ? is called the connecting coalition number, ?(G). Some bounds on the coalition number ?(G) are found, and graphs having ?(G) = 2 are characterized. Further, the existence of connecting coalition partitions in graphs is explored. 2025 World Scientific Publishing Company. -
Introduction to connecting coalitions
A connecting coalition in a graph G(V;E) consists of two disjoint vertex subsets V1 and V2 of V (G), where neither G[V1] nor G[V2] is a connected graph but G[V1 [V2] is a con- nected graph. A connecting coalition partition is a vertex partition ? = fV1; V2; : : : ; Vkg, and the maximum cardinality of all possible ? is called the connecting coalition number, ?(G). Some bounds on the coalition number ?(G) are found, and graphs having ?(G) = 2 are characterized. Further, the existence of connecting coalition partitions in graphs is explored. 2025 World Scientific Publishing Company. -
Secure equitable domination in Cartesian product of graphs
In graphs, several domination parameters have been introduced by incorporating a combination of the existing ones. A secure equitable domination is a domination in which the dominating set admits the properties of both; secure as well as equitable dominating sets. An equitable dominating set D of a graph G is said to be secure equitable dominating set, if for every u ? V?D, there exists a vertex v ? D such that u and v are adjacent and {D?{v}}?{u} is an equitable dominating set of G. The minimum cardinality of a secure equitable dominating set of G is called the secure equitable domination number of G. In this paper, we study certain cases were the secure domination, the equitable domination and the secure equitable domination bounds are equal. Moreover, we establish the bounds of secure equitable domination number of the Cartesian product of graphs. 2025 World Scientific Publishing Company. -
Domination-related colorings of n-inordinate invariant intersection graphs
Algebraic graph theory is an intriguing field of research in which various properties of graphs constructed based on algebraic structures are studied. Interlacing two important structural aspects of graphs namely, coloring, and domination in graphs, several domination-related colorings of graphs are introduced in the literature. In this paper, we study such domination-related colorings of algebraic graphs, called the n-inordinate invariant intersection graphs and the n-inordinate invariant non-intersection graphs, that are constructed based on the symmetric group. 2025 World Scientific Publishing Company. -
Forbidden subgraphs and prohibited colorings for vertex identification in graphs
A red-white coloring of a graph G of diameter d is done by assigning the colors red and white to the vertices of the graph such that, there should be at least one red vertex. Then, each of the vertices is assigned a vector of length d called code in which the value of ith coordinate is equal to the number of red-colored vertices at distance i from this vertex, i ? {1, 2, 3,,d}. A red-white coloring when the code assigned to each vertex is different than that coloring is called an ID-coloring and a graph which has an ID-coloring is an ID-graph. The minimum number of vertices required to be colored red to get an ID-coloring is called the ID-number. ID-coloring is not possible for all graphs. There exist many properties which prevent ID-coloring. In this paper, we explore some forbidden induced subgraphs and certain prohibited red-white colorings which prevent the existence of ID-coloring. 2025 World Scientific Publishing Company. -
Centrality-based graph entropy and sensitivity analysis of n-inordinate invariant intersection graphs
Centrality is a real-valued function on the vertex set of a graph that helps in determining the vitality of its vertices. Graph entropy gives the structural information of complex networks, based on some information of the network entities. An algebraic intersection graph called the n-inordinate invariant intersection graph has been constructed from the symmetric group and its structural properties are being studied, in the literature. In this paper, we discuss the centrality measures and the graph entropy of the n-inordinate invariant intersection graphs and their complements, and analyze the sensitivity of these networks, based on the centrality measures of their vertices. 2020 World Scientific Publishing Company. -
Coalition partitions of n-inordinate invariant intersection graphs
A class of algebraic intersection graphs, called the n-inordinate invariant intersection graphs, has been introduced and various properties of these graphs are investigated in the literature. Domination is an important structural property in graphs and the notion of coalition in graphs has been recently introduced based on different types of domination in graphs. In this article, we analyse the structure of the n-inordinate invariant intersection graphs by investigating certain variants of domination based coalition partitions of them. 2025 World Scientific Publishing Company. -
A study on the restrained domination number in diverse families of derived signed graphs
A derived graph is obtained by applying a specific graph operation to a given graph G. A set D of vertices in a signed graph ? is a restrained dominating set of ? if D is a restrained dominating set of the underlying graph |?|, and every cycle formed by the edges connecting D to V \D and those within V \D is balanced. The restrained domination number ?r(?) is the minimum cardinality of a restrained dominating set of ?. In this paper, we establish results on the restrained domination number for derived signed graphs, including line signed graphs, semi-total point signed graphs, semi-total line signed graphs, and total signed graphs and we also examine their structural properties in relation to their restrained domination number. 2025 World Scientific Publishing Company. -
Restrained geodetic domination polynomial
For a connected graph G = (V, E), a vertex subset S of G is said to be a restrained geodetic dominating set if S is both geodetic and dominating set of G and also, the subgraph induced by V ? S consists of no vertex with degree zero. From the study of domination polynomial and geodetic domination polynomial, we have initiated the study on restrained geodetic domination polynomial. World Scientific Publishing Company. -
Further studies on chromatic completion of graphs
The chromatic completion graph of G with respect to a proper vertex coloring c of G, denoted by Gc?, is the graph obtained by adding all possible edges to G without violating the proper coloring protocol. The maximum number of edges added to G to obtain the chromatic completion graph is the chromatic completion number ??(G). Equitable chromatic completion graph Ge? of a graph G and equitable chromatic completion number ??e(G) are the equitable analogues of Gc? and ??(G), respectively. In this paper, we present various structural aspects of chromatic completion graphs and equitable chromatic completion graphs. Also, the chromatic completion and the related parameter are described in terms of adjacency matrix and color matrix of graphs. The equitable chromatic completion graph is shown to be a Tur graph. More relevantly, we obtained the equitable chromatic completion number of an arbitrary graph G. World Scientific Publishing Company. -
Some improper injective coloring parameters of graphs
Any vertex coloring protocol of a graph can be viewed as a random experiment of assigning colors to the vertices, whose random variable is defined as the number of vertices assigned a specific color in that coloring. Based on this idea, the statistical parameters of mean and variance have been extended to chromatic mean and chromatic variance for various proper vertex colorings of graphs in the literature. In this paper, the ideas of chromatic mean and chromatic variance of graphs concerning their improper injective coloring are introduced and determined for certain standard graphs. World Scientific Publishing Company. -
Antimagic labeling of n-uniform cactus chain graphs
A graph G = (V,E) is considered antimagic if it admits antimagic labeling. The antimagic labeling of a finite, simple graph with |V | = n and |E| = m is a bijective function from the set of edges to the set of integers {1, 2,,m} such that the vertex sum of n vertices is pairwise distinct. The vertex sum of a vertex is obtained by summing the labels of all edges incident to it. Hartsfield and Ringel conjectured that every connected graph different from K2 is antimagic. Supporting this conjecture, it was shown that the dense graphs are antimagic. A cactus graph is a connected graph where no edge lies within more than one cycle. A cactus graph in which each block is a cycle of the same size n is called an n-uniform cactus graph. We proved that Hartsfield and Ringels conjecture is true for n-uniform cactus chain graphs with and without pendant vertices, which are specific cases of sparse graphs. 2026 World Scientific Publishing Company. -
Bounds on Sombor index of graph operations
Operations in graph theory have a significant influence in the theoretical and application aspect of the domain. Topological indices serve as a crucial component in chemical graph theory linked with some molecular structure. Recently, Gutman initiated the study on the Sombor index. In this paper, the computation of some bounds for Sombor index of graph operation notably join, cartesian product, corona product, lexicographic product, tensor product and strong product is carried out. The computation has been utilized to determine the upper bounds of the index for the specified graph operations for some standard graphs like the path and cycle graphs. 2025 World Scientific Publishing Company. -
Centrality measures-based sensitivity analysis and entropy of nonzero component graphs
The nonzero component graph of a finite-dimensional vector space over a finite field is a graph whose vertices are the nonzero vectors in the vector space, and any two vertices are adjacent if the corresponding linear combination contains a common basis vector. In this paper, we discuss the centrality measures and entropy of the nonzero component graph and also analyze the sensitivity of the graph using the centrality measures. 2025 World Scientific Publishing Company. -
Edge incident 2-edge coloring of graphs
The edge incident 2-edge coloring of a graph G is an edge coloring of the graph G such that not more than two colors are assigned to the edges incident to an edge e = uv in G. In other words, for every edge e in G, the edge e and all the edges that are incident to the edge e is in at most two different color classes. The edge incident 2-edge coloring number ?'ein2 (G) is the maximum number of colors in any edge incident 2-edge coloring of G. The main objective of this paper is to study the edge incident 2-edge coloring concept and apply the same to some graph classes. Besides finding the exact values of these parameters, we also obtain some bounds. 2025 World Scientific Publishing Company. -
Chromatic bounds of some (P5, banner)-free graphs
Let ?(G) and ?(G), respectively, denote the chromatic number and clique number of a graph G. A P5 is a path on five vertices, a banner (paw) is the graph obtained by joining a new vertex to a single vertex of C4 (C3) and a hammer is obtained by subdividing the pendant edge of a paw exactly once. Recently, (P5,banner)-free graphs have received wide attention. In 2019, Karthick, Maffray and Pastor, gave a structural characterisation of (P5,banner)-free graphs, which when combined with a result by Bourneuf and Thomass[Bounded twin-width graphs are polynomially ?-bounded, Adv. Comb. (2025)] implies that for a (P5,banner)-free graph G, ?(G) ? ?(G)5. Geir [Colourings of P5-Free Graphs, PhD Thesis, Technische Universit at Bergakademie Freiberg (2022)] showed that the ?-binding function of the class of (P5,banner)-free graphs is bounded by the ?-binding function of 3K1-free graphs. By a result of Kim [The Ramsey number R(3,t) has order of magnitude t2/log t, Random Structures and Algorithms 7(3) (1995) 173207], the chromatic number ?(G) of a 3K1-free graph G has order of magnitude ?(?(G)2/log ?(G)). Recently, Song and Xu [Divisibility and coloring of some P5-free graphs, Discrete Appl. Math. 348 (2024) 144151] proved that every (P5, C5, banner, hammer)-free graph G is ?(G)3/2-colorable. This motivates us to study the subclasses of (P5, banner)-free graphs. We prove that for any (P5, banner, F ? K1)-free graph G where F ?{C4,K4 ? e,K3 ? K1,paw}, ?(G) ? ?(G)2/2 for ?(G) ? 3. Moreover, the bound is tight for ?(G) = 3. 2026 World Scientific Publishing Company. -
A study on the invariant intersection graph of a graph
Analyzing the structure of the automorphism groups of graphs, and investigating the properties of graphs that are constructed from algebraic structures are two important research topics in algebraic graph theory. Blending these two aspects of study, an algebraic intersection graph, called the invariant intersection graph of a graph, has been introduced in the literature. In this paper, we study certain properties of the invariant intersection graphs of graphs, and obtain some structural characterizations of these graphs, based on the automorphism group of the graph on which the invariant intersection graph is constructed. 2026 World Scientific Publishing Company. -
Cyclic property of iterative eccentrication of trees
A tree graph is an acyclic graph. The eccentric graph of a graph G, denoted by Ge is a derived graph with the vertex set same as that of G and two vertices in Ge are adjacent if one of them is an eccentric vertex of the other. The process of finding eccentric graph of a graph is called eccentrication and that of constructing iterative eccentric graphs, denoted by Gek, is called iterative eccentrication. A graph G is said to be ?-cyclic(t,l) if G, Ge, Ge2,?, Gek, Gek+1,?, Gek+l are the only non-isomorphic graphs, and the graph Gek+l+1 is isomorphic to Gek. In this paper, we prove the existence of an ?-cycle for any tree graph on n vertices. We also obtain some important results on eccentric graphs of trees. Then, we present a conjecture on the cyclic property of eccentrication of a general graph G. Finally, an analogy between the concept of ?-cycle for a graph and the dichotomy of the Riemann sphere into Fatou sets and Julia sets is presented. We also state some open problems in the area. 2025 World Scientific Publishing Company. -
Certain variants of domatic partitions of n-inordinate invariant intersection graphs
A class of algebraic intersection graphs, called the n-inordinate invariant intersection graphs, are introduced in the literature and several properties of these graphs are being investigated. Domination in graphs is an important structural property and partitioning the vertex set of a graph into dominating sets is called the domatic partition of a graph. In this paper, we analyze the structure of the n-inordinate invariant intersection graphs by investigating certain variants of domatic partitions of these graphs, that are defined based on different types of domination in graphs. 2026 World Scientific Publishing Company. -
Some new results on anti-adjacency spectra of regular graphs
The anti-adjacency matrix A*(G) of a simple graph G with V (G) = {v1,v2,v3,vn}, is a square matrix of order n with rows and columns indexed by V (G), where the (i,j)-entry (i?j) is 1, if the vertices vi and vj are not adjacent to each other and 0, otherwise. The (i,i)- entry of A*(G) is 1. The anti-adjacency eigenvalues of G are the eigenvalues obtained from the matrix A*(G) and the corresponding spectra is called the anti-adjacency spectra of G, denoted by a-spec(G). In this paper, we discuss the anti-adjacency spectra of join and disjoint union of regular graphs. The anti-adjacency spectra of bipartite regular graphs, line graphs of regular graphs and strongly regular graphs are also discussed. 2026 World Scientific Publishing Company.