Search

In this paper, we study the class of graphs G m , n that have the same degree sequence as two disjoint cliques K m and K n , as well as the class G ¯ m , n of the complements of such graphs. The problems of finding a maximum clique and a maximum independent set are NP-hard on G m , n . Therefore, looking for upper and lower bounds for the clique and independence numbers of such graphs is a challenging task. In this article, we obtain such bounds, as well as other related results. In particular, we consider the class of regular graphs, which are degree-equivalent to arbitrarily many identical cliques, as well as such graphs of bounded degree. [ABSTRACT FROM AUTHOR]

Let S be a Clifford semigroup and A a subset of S. We write C a y (S , A) for the Cayley digraph of a Clifford semigroup S relative to A. The (weak, path, weak path) independence number of a graph is the maximum cardinality of an (weakly, path, weakly path) independent set of vertices in the graph. In this paper, we characterize maximal connected subdigraphs of C a y (S , A) and apply these results to determine the (weak, path, weak path) independence number of C a y (S , A) . [ABSTRACT FROM AUTHOR]

Win proved a very famous conclusion that states the graph G with connectivity κ (G) , independence number α (G) and α (G) ≤ κ (G) + k − 1 (k ≥ 2) contains a spanning k-ended tree. This means that there exists a spanning tree with at most k leaves. In this paper, we strengthen the Win theorem to the following: Let G be a simple 2-connected graph such that | V (G) | ≥ 2 κ (G) + k , α (G) ≤ κ (G) + k (k ≥ 2) and the number of maximum independent sets of cardinality κ + k is at most n − 2 κ − k + 1 . Then, either G contains a spanning k-ended tree or a subgraph of K κ ∨ ((k + κ − 1) K 1 ∪ K n − 2 κ − k + 1) . [ABSTRACT FROM AUTHOR]

In mathematical chemistry, molecular descriptors serve an important role, primarily in quantitative structure–property relationship (QSPR) and quantitative structure–activity relationship (QSAR) studies. A topological index of a molecular graph is a real number that is invariant under graph isomorphism conditions and provides information about its size, symmetry, degree of branching, and cyclicity. For any graph N, the first and second Gourava indices are defined as G O 1 (N) = ∑ u ′ v ′ ∈ E (N) (d (u ′) + d (v ′) + d (u ′) d (v ′) ) and G O 2 (N) = ∑ u ′ v ′ ∈ E (N) (d (u ′) + d (v ′)) d (u ′) d (v ′) , respectively.The independence number of a graph N, being the cardinality of its maximal independent set, plays a vital role in reading the energies of chemical trees. In this research paper, it is shown that among the family of trees of order δ and independence number ξ , the spur tree denoted as Υ δ , ξ maximizes both 1st and 2nd Gourava indices, and with these characterizations this graph is unique. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph, and let β ∈ R . Motivated by a service coverage maximization problem with limited resources, we study the β -differential of G. The β-differential of G, denoted by ∂ β (G) , is defined as ∂ β (G) : = max { | B (S) | − β | S | s u c h t h a t S ⊆ V } . The case in which β = 1 is known as the differential of G, and hence ∂ β (G) can be considered as a generalization of the differential ∂ (G) of G. In this paper, upper and lower bounds for ∂ β (G) are given in terms of its order | G | , minimum degree δ (G) , maximum degree Δ (G) , among other invariants of G. Likewise, the β -differential for graphs with heavy vertices is studied, extending the set of applications that this concept can have. [ABSTRACT FROM AUTHOR]

The cardinality of a largest independent set of G, denoted by α (G) , is called the independence number of G. The independent domination number i (G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by α c (G) , as the greatest integer r such that every vertex of G belongs to some independent subset X of V G with | X | ≥ r . The common independence number α c (G) of G is the limit of symmetry in G with respect to the fact that each vertex of G belongs to an independent set of cardinality α c (G) in G, and there are vertices in G that do not belong to any larger independent set in G. For any graph G, the relations between above parameters are given by the chain of inequalities i (G) ≤ α c (G) ≤ α (G) . In this paper, we characterize the trees T for which i (T) = α c (T) , and the block graphs G for which α c (G) = α (G) . [ABSTRACT FROM AUTHOR]

For any graph G of order p, a bijection f : V (G) → { 1 , 2 , ... , p } is called a numbering of G. The strength s t r f (G) of a numbering f of G is defined by s t r f (G) = max { f (u) + f (v) | u v ∈ E (G) } , and the strength s t r (G) of a graph G is s t r (G) = min { s t r f (G) | f   is   a   numbering   of   G }. In this paper, many open problems are solved, and the strengths of new families of graphs are determined. [ABSTRACT FROM AUTHOR]

The concept of Sombor index (S O) was recently introduced by Gutman in the chemical graph theory. It is a vertex-degree-based topological index and is denoted by Sombor index S O : S O = S O (G) = ∑ v i v j ∈ E (G) d G (v i) 2 + d G (v j) 2 , where d G (v i) is the degree of vertex v i in G. Here, we present novel lower and upper bounds on the Sombor index of graphs by using some graph parameters. Moreover, we obtain several relations on Sombor index with the first and second Zagreb indices of graphs. Finally, we give some conclusions and propose future work. [ABSTRACT FROM AUTHOR]

Let G be a graph, for any real 0 ≤ α ≤ 1 , Nikiforov defines the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , where A (G) and D (G) are the adjacency matrix and diagonal matrix of degrees of the vertices of G. This paper presents some extremal results about the spectral radius ρ α (G) of the matrix A α (G) . In particular, we give a lower bound on the spectral radius ρ α (G) in terms of order and independence number. In addition, we obtain an upper bound for the spectral radius ρ α (G) in terms of order and minimal degree. Furthermore, for n > l > 0 and 1 ≤ p ≤ ⌊ n − l 2 ⌋ , let G p ≅ K l ∨ (K p ∪ K n − p − l) be the graph obtained from the graphs K l and K p ∪ K n − p − l and edges connecting each vertex of K l with every vertex of K p ∪ K n − p − l. We prove that ρ α (G p + 1) < ρ α (G p) for 1 ≤ p ≤ ⌊ n − l 2 ⌋ − 1 . [ABSTRACT FROM AUTHOR]

A total dominating set D of a graph G is said to be a secure total dominating set if for every vertex u ∈ V (G) \ D , there exists a vertex v ∈ D , which is adjacent to u, such that (D \ { v }) ∪ { u } is a total dominating set as well. The secure total domination number of G is the minimum cardinality among all secure total dominating sets of G. In this article, we obtain new relationships between the secure total domination number and other graph parameters: namely the independence number, the matching number and other domination parameters. Some of our results are tight bounds that improve some well-known results. [ABSTRACT FROM AUTHOR]

For positive integers s and t, the Ramsey number R (s , t) is the smallest positive integer n such that every graph of order n contains either a clique of order s or an independent set of order t. The triangle-free process begins with an empty graph of order n, and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. It has been an important tool in studying the asymptotic lower bound for R (3 , t) . Cyclic graphs are vertex-transitive. The symmetry of cyclic graphs makes it easier to compute their independent numbers than related general graphs. In this paper, the cyclic triangle-free process is studied. The sizes of the parameter sets and the independence numbers of the graphs obtained by the cyclic triangle-free process are studied. Lower bounds on R (3 , t) for small t's are computed, and R (3 , 35) ≥ 237 , R (3 , 36) ≥ 244 , R (3 , 37) ≥ 255 , R (3 , 38) ≥ 267 , etc. are obtained based on the graphs obtained by the cyclic triangle-free process. Finally, some problems on the cyclic triangle-free process and R (3 , t) are proposed. [ABSTRACT FROM AUTHOR]

Networks have an important role in our daily lives. The effectiveness of the network decreases with the breaking down of some vertices or links. Therefore, a less vulnerable communication network is required for greater stability. Vulnerability is the measure of resistance of the network after failure of communication links. In this article, a graph has been taken for modeling a network and integrity as a measure of vulnerability. The approach is to estimate the integrity or upper bound of integrity of at least one connected graph or network constructed from the given graphic integer sequence. Experiments have been done with random graphs, complex networks and also a comparison between two parameters, namely the vertex connectivity and graph integrity as a measure of the network vulnerability have been carried out by removing vertices randomly from various complex networks. A comparison with the existing method shows that the algorithm proposed in this article provides a much better integrity measurement. [ABSTRACT FROM AUTHOR]

Graph invariants are the properties of graphs that do not change under graph isomorphisms, the independent set decision problem, vertex covering problem, and matching number problem are known to be NP-Hard, and hence it is not believed that there are efficient algorithms for solving them. In this paper, the graph invariants matching number, vertex covering number, and independence number for the zero-divisor graph over the rings Z p k and Z p k q r are determined in terms of the sets S p i and S p i q j respectively. Accordingly, a formula in terms of p , q , k , and r, with n = p k , n = p k q r is provided. [ABSTRACT FROM AUTHOR]