Search

The main aim of the paper is to give the crossing number of the join product G* + Dn for the graph G* isomorphic to 4-regular graph on six vertices except for two distinct edges with no common vertex such that two remaining vertices are still adjacent, and where Dn consists of n isolated vertices. The proofs are done with the help of well-known exact values for crossing numbers of join products of four subgraphs Hk of G* with discrete graphs. Further, we give a conjecture concerning crossing numbers of the join products of Dn with Wm\e for both types edges e of wheels Wm of m + 1 vertices. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A set S ⊆ V is a total restrained dominating set if every vertex is adjacent to a vertex in S , and every vertex in V − S is adjacent to a vertex in V − S. The total restrained domination number of G , denoted γ t r (G) , is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K 1 , ℓ -free graph with δ ≥ ℓ ≥ 3 and δ ≥ 5 , then γ t r (G) ≤ n 1 − (2 δ − 3) (2 δ) δ δ − 1 + o δ (1) . [ABSTRACT FROM AUTHOR]

An isolating set in a graph is a set X of vertices such that every edge of the graph is incident with a vertex of X or its neighborhood. The isolation number of a graph, or equivalently the vertex-edge domination number, is the minimum number of vertices in an isolating set. Caro and Hansberg, and independently Żyliński, showed that the isolation number is at most one-third the order for every connected graph of order at least 6. We show that in fact all such graphs have three disjoint isolating sets. Further, using a family introduced by Lemańska, Mora, and Souto-Salorio, we determine all graphs with equality in the original bound. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple graph. A set D ⊆ V is a strong dominating set of G, if for every vertex x ∈ V \ D there is a vertex y ∈ D with xy ∈ E(G) and deg(x) ≤ deg(y). The strong domination number γst(G) is defined as the minimum cardinality of a strong dominating set. In this paper, we study the strong domination number of Hajós sum and vertex-sum of two graphs. [ABSTRACT FROM AUTHOR]

Claude Berge (1987) introduced the concept of k-extendable graphs, wherein any independent set of size k is inherently a constituent of a maximum independent set within a graph H = (V , E) . Graphs possessing the property of being 1-extendable are termedas Berge graphs. This introduction gave rise to the notion of well-covered graphs and well-dominated graphs. A graph is categorized as well-covered if each of its maximal independent sets is, in fact, a maximum independent set. Similarly, a graph attains the classification of well-dominated if every minimal dominating set (DS) within it is a minimum dominating set. In alignment with the concept of k-extendable graphs, the framework of (k , γ) -endowed graphs and symmetric (k , γ) -endowed graphs are established. In these graphs, each DS of size k encompasses a minimum DS of the graph. In this article, a study of γ -endowed dominating sets is initiated. Various results providing a deep insight into γ -endowed dominating sets in graphs such as those characterizing the ones possessing a unique minimum DS are proven. We also introduce and study the symmetric γ -endowed graphs and minimality of dominating sets in them. In addition, we give a solution to an open problem in the literature. which seeks to find a domination-based parameter that has a correlation coefficient of ρ > 0.9967 with the total π -electronic energy of lower benzenoid hydrocarbons. We show that the upper dominating number Γ (H) studied in this paper delivers a strong prediction potential. [ABSTRACT FROM AUTHOR]

Let I be the edge ideal of a connected non-bipartite graph and R the base polynomial ring. Then, depth R / I ≥ 1 and depth R / I t = 0 for t ≫ 1 . This paper studies the problem when depth R / I t = 1 for some t ≥ 1 and whether the depth function is non-increasing thereafter. Furthermore, we are able to give a simple combinatorial criterion for depth R / I (t) = 1 for t ≫ 1 and show that the condition depth R / I (t) = 1 is persistent, where I (t) denotes the t-th symbolic powers of I. [ABSTRACT FROM AUTHOR]

For a graph Γ , a subset S ⊆ V Γ is known to be a dominating set, if every x ∈ V Γ \ S has at least one neighbor in D. The domination number γ (Γ) is merely the size of a smallest dominating set in Γ . The strong product P r ⊠ P s of two paths P r and P s is known as the king's graph. Interestingly, the king's graph is isomorphic to the two-parametric family of cellular neural network (CNNs). In Asad et al. (Alex Eng J 66:957–977, 2023), the authors retrieved certain structural characteristics of CNNs from their minimal dominating sets. They conjectured in Problem 8.3 that the domination number of P r ⊠ P s is ⌈ r 3 ⌉ ⌈ s 3 ⌉ . This paper solves Problem 8.3 by providing a proof to the conjecture. This result, in turn, reveals interesting topological properties such as an optimal routing for this class of neural networks. [ABSTRACT FROM AUTHOR]

In this paper we show the relationship between global offensive alliance and dominant sets in the graphs and the random graphs. A global offensive alliance in a graph G=(V, E) is a subset S of V such that for every vertex v not in S at least half of the vertices in the closed neighbourhood of v are in S and a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbour in D. [ABSTRACT FROM AUTHOR]

Let Heff (Veff, Eeff) be a finite simple connected graph of order m with vertex set Veff and edge set Eeff. A dominating set S d s ⊆ V e f f is called an efficiently dominating set if, for every vertex u a ∈ V G ,   N G u a ∩ S d s = 1 —where NG [ua] denotes the closed neighborhood of the vertex ua. Using efficient domination techniques and labelling, we constructed the fuzzy network. An algorithm has been framed to encrypt and decrypt the secret information present in the network, and furthermore, the algorithm has been given in pseudocode. The mathematical modelling of a strong fuzzy network is defined and constructed to elude the burgeoning intruder. Using the study of the efficient domination of fuzzy graphs, this domination parameter plays a nuanced role in encrypting and decrypting the framed network. One of the main purposes of fuzzy networks is encryption, so one of our contributions to this research is to build a novel combinatorial technique to encrypt and decode the built-in fuzzy network with a secret number utilizing effective domination. An illustration with an appropriate secret message is provided along with the encryption and decryption algorithms. Furthermore, we continued this study in intuitionistic fuzzy networks. [ABSTRACT FROM AUTHOR]

For a graph  G = (V , E)  and a function  f : V → { − 1 , + 1 } , if  S ⊆ V  then we write  f (S) = ∑ v ∈ S f (v) . A function  f  is said to be a non-zero vertex signed dominating function (for short, NVSDF) of  G  if  f (N [ v ]) = 0  holds for every vertex  v  in  G , and the non-zero vertex signed domination number of  G  is defined as  γ s b (G) = max { f (V) | f   is   an   NVSDF   of   G }.  In this paper, the novel concept of the non-zero vertex signed domination for graphs is introduced. There is also a special symmetry concept in graphs. Some upper bounds of the non-zero vertex signed domination number of a graph are given. The exact value of  γ s b (G)  for several special classes of graphs is determined. Finally, we pose some open problems. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G = (V , E) is a subset of vertices S ⊆ V such that every vertex v ∈ V ∖ S has at least one neighbor in S. Finding a dominating set with the minimum cardinality in a connected graph G = (V , E) is known to be NP-hard. A polynomial-time approximation algorithm for this problem, described here, works in two stages. At the first stage a dominant set is generated by a greedy algorithm, and at the second stage this dominating set is purified (reduced). The reduction is achieved by the analysis of the flowchart of the algorithm of the first stage and a special kind of clustering of the dominating set generated at the first stage. The clustering of the dominating set naturally leads to a special kind of a spanning forest of graph G , which serves as a basis for the second purification stage. We expose some types of graphs for which the algorithm of the first stage already delivers an optimal solution and derive sufficient conditions when the overall algorithm constructs an optimal solution. We give three alternative approximation ratios for the algorithm of the first stage, two of which are expressed in terms of solely invariant problem instance parameters, and we also give one additional approximation ratio for the overall two-stage algorithm. The greedy algorithm of the first stage turned out to be essentially the same as the earlier known state-of-the-art algorithms for the set cover and dominating set problem Chvátal [6] and Parekh [31]. The second purification stage results in a significant reduction of the dominant set created at the first stage, in practice. The practical behavior of both stages was verified for randomly generated problem instances. The computational experiments emphasize the gap between a solution of Stage 1 and a solution of Stage 2. [ABSTRACT FROM AUTHOR]

This work presents some random graphs with their dominating sets found by us. After giving an overview of the literature related to the topic and the route of scientific development leading to the definition of the random graphs, the logical process leading to the dominating sets of random graphs has been presented. [ABSTRACT FROM AUTHOR]

Graphs of order n with fault-tolerant metric dimension n have recently been characterized.This paper points out an error in the proof of this characterization. We show that the complete multipartite graphs also have the fault-tolerant metric dimension n, which provides an infinite family of counterexamples to the characterization. Furthermore, we find exact values of the metric, edge metric, mixed-metric dimensions, the domination number, locating-dominating number, and metric-locating-dominating number for the complete multipartite graphs. These results generalize various results in the literature from complete bipartite to complete multipartite graphs. [ABSTRACT FROM AUTHOR]

The secure domination numbers of the Cartesian products of two small graphs with paths or cycles is determined, as well as for Möbius ladder graphs. Prior to this work, in all cases where the secure domination number has been determined, the proof has either been trivial, or has been derived from lower bounds established by considering different forms of domination. However, the latter mode of proof is not applicable for most graphs, including those considered here. Hence, this work represents the first attempt to determine secure domination numbers via the properties of secure domination itself, and it is expected that these methods may be used to determine further results in the future. [ABSTRACT FROM AUTHOR]

To monitor electrical activity throughout the power grid and mitigate outages, sensors known as phasor measurement units can installed. Due to implementation costs, it is desirable to minimize the number of sensors deployed while ensuring that the grid can be effectively monitored. This optimization problem motivates the graph theoretic power dominating set problem. In this paper, we propose a method for computing minimum power dominating sets via a set cover IP formulation and a novel constraint generation procedure. The set cover problem's constraints correspond to neighborhoods of zero forcing forts; we study their structural properties and show they can be separated with delayed row generation. In addition, we offer several computation enhancements which be be applied to our methodology as well as existing methods. The proposed and existing methods are evaluated in several computational experiments. In many of the larger test instances considered, the proposed method exhibits an order of magnitude runtime performance improvement. [ABSTRACT FROM AUTHOR]

Let be a simple weighted undirected graph with nonnegative edge weights. Let be a minimal dominating set in . The cutset induced by is the set of edges with one vertex in the set and the other in . The weight of the cutset is the total weight of all its edges. The paper deals with the problem of finding a cutset with the maximum weight among all minimal dominating sets. In particular, the nonexistence of a polynomial approximation algorithm with a ratio better than in the case of is proved. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple graph. A set M ⊆ E is a matching if no two edges in M have a common vertex. The matching number, denoted β (G) (or β ), is the maximum size of a matching in G. A double Roman dominating function (DRDF) on a graph G is a function f: V ⟶ { 0 , 1 , 2 , 3 } satisfying the conditions that for every vertex u of weight f (u) ∈ 0 , 1 : i if f (u) = 0 , then u is adjacent to either at least one vertex v with f (v) = 3 or two vertices v 1 , v 2 with f (v 1) = f (v 2) = 2 . i i if f (u) = 1 , then u is adjacent to at least one vertex v with f (v) ∈ 2 , 3 . The weight of a double Roman dominating function f is the value f (V) = ∑ u ∈ V f (u) . The minimum weight of a double Roman dominating function on a graph G is called the double Roman domination number of G, denoted by γ dR G . In this paper, first, we note that γ dR (G) ≤ 3 β (G) , where G is a graph without isolated vertices. Moreover, we give a descriptive characterization of block graphs G satisfying γ dR (G) = 3 β (G) . Finally, we show that the decision problem associated with γ dR (G) = 3 β (G) is C O - NP -complete for bipartite graphs. [ABSTRACT FROM AUTHOR]

Dominating set, minimum dominating set and minimum connected dominating set is correct sequence need to study in any wireless network system. One must need to have MCDS for efficient and cost effective wireless network system. A graph G = (V; E), a dominating set D is a subset of V such that any vertex not in D is adjacent to at least one vertex in D. In a graph G = (V; E) a connected dominating set is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum connected dominating set is such a vertex subset with minimum cardinality. In this paper, we present a new method i.e. AJK algorithm we can easily find a minimum connected dominating set. We can easily see that this algorithm gives a constant performance guarantee. The results show that, despite its simplicity, the proposed algorithm gives very good solutions. [ABSTRACT FROM AUTHOR]

In this paper analyses the concept of domination and its characteristics in graph theory. Here the concept of Domination, Maximum Dominating Set and Maximal Dominating Set as well as the concept of Independent set, Maximum Independent set and Maximal Independent Set are discussed in further. Dominating set is the collection of possible non-touching vertices through the single edge. Maximum Dominating set consist maximum number of possible non-touching vertices in the given graph. Maximal Domination Set consist minimum number of possible non-touching vertices which is adjacent with all the edges in the graph. Various types of Graphs, Structure and their properties also have to be discussed. Major part of this paper considers the cardinality calculation of Maximum and Maximal Dominating sets in the various graphs. After calculation, it derived a general formula for the calculation of Maximum Dominating cardinality and Maximal Dominating Cardinality. The calculation values should be representing in table format. [ABSTRACT FROM AUTHOR]

Positive semidefinite (PSD) zero forcing is a dynamic graph process in which an initial subset of vertices are colored and may cause additional vertices to become colored through a set of color changing rules. Subsets which cause all other vertices to become colored are called PSD zero forcing sets; the PSD zero forcing number of a graph is the minimum cardinality attained by its PSD zero forcing sets. The PSD zero forcing number is of particular interest as it bounds solutions for the minimum rank and PSD min rank problems, both popular in linear algebra. This paper introduces blocking sets for PSD zero forcing sets which are used to formulate the first integer program (IP) for computing PSD zero forcing numbers of general graphs. It is shown that facets of the feasible region of this IP's linear relaxation correspond to zero forcing forts which induce connected subgraphs, but that identifying min cardinality connected forts is NP‐hard in general. Auxiliary IPs used to find these blocking sets are also given, enabling the master IP to be solved via constraint generation. Experiments comparing the proposed methods and existing algorithms are provided demonstrating improved runtime performance, particularly so in dense and sparse graphs. [ABSTRACT FROM AUTHOR]

The deployment problem of sensor nodes of Internet of things (IoT) can be abstracted as listing minimal dominating sets of a graph. The problem of listing all the minimal dominating sets in a graph can be converted to the problem of state space search among candidate vertex sets. The search and optimization technologies, such as the bidirectional search and branch cut, can be applied to solve the problem effectively. Our experiments show that the new algorithm can reduce the running time by at least an order of magnitude, compared to a state-of-the-art algorithm for listing all the minimal dominating sets. [ABSTRACT FROM AUTHOR]

A restricted minus dominating function on a graph G = (V;E) is a function f : V ! f-1; 0; 1g such that f(N[v]) 0 for every vertex v 2 V and a vertex assigned 0 is adjacent to at least one vertex assigned 1. The restricted minus domination number r (G) = minfw(f) : f is restricted minus dominating functiong. In this paper, we initiate the study of r (G) and its relationship with sign and minus domination are investigated. Many of the known bounds of r (G) are immediate consequence of our results. [ABSTRACT FROM AUTHOR]

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C (x) denote the set of colors of vertex x and of the edges incident with x, we call C (x) the color set of x. If C (u) = C (v) for any two different vertices u and v of V (G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by xeVt (G) and is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K7,n (n ≥ 978) is discussed in this paper and the VDET chromatic number of K7,n (n ≥ 978) has been obtained. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G = (V,E) is a subset D of V such that every vertex not in D is adjacent to at least one vertex in D. A dominating set D is a total dominating set, if every vertex in V is adjacent to at least one vertex in D. The set P is said to be an open packing set if no two vertices of P have a common neighbor in G. In this paper, we obtain domination number, total domination number and open packing number of the molecular graph of a new type of graphene named CorCor that is a 2-dimensional carbon network. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple graph of order n. The total dominating set of G is a subset D of V that every vertex of V is adjacent to some vertices of D. The total domination number of G is equal to minimum cardinality of total dominating set in G and is denoted by t(G). The total domination polynomial of G is the polynomial Dt(G, x) = ... dt(G, i)xi, where dt(G, i) is the number of total dominating sets of G of size i. A root of Dt(G, x) is called a total domination root of G. The set of total domination roots of graph G is denoted by Z(Dt(G, x)). In this paper, we show that Dt(G, x) has δ-2 non-real roots and if all roots of Dt(G, x) are real, then δ ≤ 2, where δ is the minimum degree of vertices of G. Also we show that if δ ≥ 3 and Dt(G, x) has exactly three distinct roots, then Z(Dt(G, x)) ⊆ {0, ... }. Finally we study the location roots of total domination polynomial of some families of graphs. [ABSTRACT FROM AUTHOR]

The independent domination number γ i (G) of a graph G is the maximum, over all independent sets I, of the minimal number of vertices needed to dominate I. It is known (Aharoni et al. in Combinatorica 22:335–343, 2002) that in chordal graphs γ i is equal to γ , the ordinary domination number. The weighted version of this result is not true, but we show that it does hold for interval graphs, and for the intersection graphs of subtrees of a given tree, where each subtree is a single edge. [ABSTRACT FROM AUTHOR]

Abstract Let G = (V , E) be a graph. A set S ⊆ V is a total restrained dominating set if every vertex is adjacent to a vertex in S , and every vertex in V − S is adjacent to a vertex in V − S. The total restrained domination number of G , denoted γ t r (G) , is the smallest cardinality of a total restrained dominating set of G. In Koh et al. (2013), it is proved that if G is a graph of order n ≥ 4 and δ (G) ≥ 2 , then γ t r (G) ≤ n − n 4 3. It is further conjectured that this bound can be improved to γ t r (G) ≤ n − θ (n). In this paper we show that if G is a graph with no C 3 components and δ (G) ≥ 2 , then γ t r (G) ≤ n − n 2 . [ABSTRACT FROM AUTHOR]

Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by $in_{cc} (G)$, is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S.In this work, first we provide bounds on $in_{cc} (G)$ and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = N P ).On the positive side, we present polynomial-time algorithms to compute $in_{cc} (G)$ for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q − 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G.Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems.

Now define S a cartesian product of finite times with S M n which is a finite semigroup having elements { 0 , x , x 2 , … , x n } of order n . Γ( S ) is an undirected graph whose vertices are the nonzero elements of S . It is a new graph type which is the dot product. k be finite positive integer for 0 ≤ { i t } t = 1 k , { j t } t = 1 k ≤ n , any two distinct vertices of S ( x i 1 , x i 2 , … , x i k ) and ( x j 1 , x j 2 , … , x j k ) are adjacent if and only ( x i 1 , x i 2 , … , x i k ) · ( x j 1 , x j 2 , … , x j k ) = 0 S M n (under the dot product) and it is assumed x i t = 0 S M n if i t = 0 . In this study, the value of diameter, girth, maximum and minimum degrees, domination number, clique and chromatic numbers and in parallel with perfectness of Γ( S ) are elucidated. [ABSTRACT FROM AUTHOR]

Harary and Norman introduced the Line graph L(G). We introduced the split complement line domonation number by posting the disconnected property on the dominating sets of L(G). In this paper, we study the connectedness property of dominating sets of L(G) by defining non-split domination parameter. Also, we studied its graph theoretical properties in terms of elements of G. [ABSTRACT FROM AUTHOR]

This paper is a survey on the upper and lower bounds for the largest eigenvalue of the Laplacian matrix, known as the Laplacian spectral radius, of a graph. The bounds are given as functions of graph parameters like the number of vertices, the number of edges, degree sequence, average 2-degrees, diameter, covering number, domination number, independence number and other parameters. [ABSTRACT FROM AUTHOR]