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]

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 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]