Search

Harary and Wiener indices are distance-based topological index. In this paper, we study the relations of graph energy e(G) and its Harary index H(G) and Wiener index W(G). Moreover, for a given graph G we study the lower bound of H(G) e(G) and W(G) e(G) in terms of the number of vertices of G. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Xinjiang University (Natural Science Edition) is the property of Xinjiang University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Let G be a k -uniform hypergraph with vertex set V (G) and edge set E (G). A connected and acyclic hypergraph is called a supertree. For 0 ≤ α < 1 , the α -spectral radius of G is the largest H -eigenvalue of α D (G) + (1 − α) A (G) , where D (G) and A (G) are the diagonal tensor of the degrees and the adjacency tensor of G , respectively. In this paper, we determine the unique supertrees with maximum α -spectral radius among all k -uniform supertrees with m edges and independence number β for ⌈ m (k − 1) + 1 k ⌉ ≤ β ≤ m , among all k -uniform supertrees with given degree sequences, and among all k -uniform supertrees with m edges and matching number μ for 1 ≤ μ ≤ ⌊ m (k − 1) + 1 k ⌋ , respectively. [ABSTRACT FROM AUTHOR]

A k -CEC graph is a graph G which has connected domination number Yc(G) = k and Yc(G+uv) < k for every uv ∈ E(G). A k-CVC graph G is a 2-connected graph with γc(G) = k and γc(G - v) < k for any v ∈ V (G). A graph is said to be maximal k-CVC if it is both k-CEC and k-CVC. Let δ, κ, and α be the minimum degree, connectivity, and independence number of G, respectively. In this work, we prove that for a maximal 3-CVC graph, if α = κ, then κ = δ. We additionally consider the class of maximal 3-CVC graphs with α < κ and κ < δ, and prove that every 3-connected maximal 3-CVC graph when κ < δ is Hamiltonian connected. [ABSTRACT FROM AUTHOR]

We continue the study of (tw , ω) -bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has useful algorithmic implications for the Maximum Independent Set and related problems. In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. II. Tree-independence number, J. Comb. Theory, Ser. B, 164 (2024) 404–442], we introduced the tree-independence number , a min-max graph invariant related to tree decompositions. Bounded tree-independence number implies both (tw , ω) -boundedness and the existence of a polynomial-time algorithm for the Maximum Weight Independent Packing problem, provided that the input graph is given together with a tree decomposition with bounded independence number. In particular, this implies polynomial-time solvability of the Maximum Weight Independent Set problem. In this paper, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. The induced minor relation is of particular interest: we show that excluding either a K 5 minus an edge or the 4-wheel implies the existence of a tree decomposition in which every bag is a clique plus at most 3 vertices, while excluding a complete bipartite graph K 2 , q implies the existence of a tree decomposition with independence number at most 2 (q − 1). These results are obtained using a variety of tools, including ℓ -refined tree decompositions, SPQR trees, and potential maximal cliques, and actually show that in the bounded cases identified in this work, one can also compute tree decompositions with bounded independence number efficiently. Applying the algorithmic framework provided by the previous paper in the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes, each of which properly contains the class of chordal graphs. In particular, these results apply to the class of 1-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019. [ABSTRACT FROM AUTHOR]

The comaximal intersection graph CI(R) of ideals of a ring R is an undirected graph whose vertex set is the collection of all non-trivial (left) ideals of R and any two vertices I and J are adjacent if and only if I + J = R and I ∩ J 6= 0. We study the connectedness of CI(R). We also discuss independence number, clique number, domination number, chromatic number of CI(R). [ABSTRACT FROM AUTHOR]

Let G be a graph, and let λ (G) denote the smallest eigenvalue of G. First, we provide an upper bound for λ (G) based on induced bipartite subgraphs of G. Consequently, we extract two other upper bounds, one relying on the average degrees of induced bipartite subgraphs and a more explicit one in terms of the chromatic number and the independence number of G. In particular, motivated by our bounds, we introduce two graph invariants that are of interest on their own. Finally, special attention goes to the investigation of the sharpness of our bounds in various classes of graphs as well as the comparison with an existing well-known upper bound. [ABSTRACT FROM AUTHOR]

Given a graph G without isolated vertices, a function f : V (G) → { 0 , 1 , 2 } is a covering total Italian dominating function if (i) the set of vertices labeled with 0 forms an independent set; (ii) every vertex labeled with 0 is adjacent to two vertices labeled with 1 or to one vertex labeled with 2; and (iii) the set of vertices labeled with 1 or 2 forms a total dominating set. The covering total Italian domination number of G is the smallest possible value of the sum ∑ v ∈ V (G) f (v) among all possible covering total Italian dominating functions f on V (G). The concepts above are introduced in this article, and the study of its combinatorial and computational properties is initiated. Specifically, we show several relationships between such parameter and other domination related parameters in graphs. We also prove the NP-completeness of the related decision problem for bipartite graphs, and present some approximation results on computing our parameter. In addition, we compute the exact value of the covering total Italian domination number of some graphs with emphasis on some Cartesian products. [ABSTRACT FROM AUTHOR]

We prove that if G is a graph and f (v) ≤ 1 / (d (v) + 1 / 2) for each v ∈ V (G) , then either G has an independent set of size at least ∑ v ∈ V (G) f (v) or G contains a clique K such that ∑ v ∈ K f (v) > 1. This result implies that for any σ ≤ 1 / 2 , if G is a graph and every clique K ⊆ V (G) has at most (1 − σ) (| K | − σ) simplicial vertices, then α (G) ≥ ∑ v ∈ V (G) 1 / (d (v) + 1 − σ). Letting σ = 0 implies the famous Caro–Wei Theorem, and letting σ = 1 / 2 implies that if fewer than half of the vertices in each clique of G are simplicial, then α (G) ≥ ∑ v ∈ V (G) 1 / (d (v) + 1 / 2) , which is tight for the 5-cycle. When applied to the complement of a graph, this result implies the following new Turán stability result. If G is a K r + 1 -free graph with more than (1 − 1 / r) n 2 / 2 − n / 4 edges, then G contains an independent set I such that at least half of the vertices in I are complete to G − I. Applying this stability result iteratively provides a new proof of the stability version of Turán's Theorem in which K r + 1 -free graphs with close to the extremal number of edges are r -partite. [ABSTRACT FROM AUTHOR]

In a fractional coloring, vertices of a graph are assigned measurable subsets of the real line and adjacent vertices receive disjoint subsets; the fractional chromatic number of a graph is at most k if it has a fractional coloring in which each vertex receives a subset of [ 0 , 1 ] of measure at least 1 / k. We introduce and develop the theory of "fractional colorings with local demands" wherein each vertex "demands" a certain amount of color that is determined by local parameters such as its degree or the clique number of its neighborhood. This framework provides the natural setting in which to generalize degree-sequence type bounds on the independence number. Indeed, by Linear Programming Duality, all of the problems we study have an equivalent formulation as a problem concerning weighted independence numbers, and they often imply new bounds on the independence number. Our results and conjectures are inspired by many of the most classical results and important open problems concerning the independence number and the chromatic number, often simultaneously. We conjecture a local strengthening of both Shearer's bound on the independence number of triangle-free graphs and the fractional relaxation of Molloy's recent bound on their chromatic number, as well as a longstanding problem of Ajtai et al. on the independence number of K r -free graphs and the fractional relaxations of Reed's ω , Δ , χ Conjecture and the Total Coloring Conjecture. We prove an approximate version of the first two, and we prove "local demands" versions of Vizing's Theorem and of some χ -boundedness results. [ABSTRACT FROM AUTHOR]

In this paper, we consider the following two problems: (i) Deletion Blocker (α) where we are given an undirected graph G = (V , E) and two integers k , d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with | S | ≤ k such that α (G − S) ≤ α (G) − d , that is the independence number of G decreases by at least d after having removed the vertices from S ; (ii) Transversal (α) where we are given an undirected graph G = (V , E) and two integers k , d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with | S | ≤ k such that for every maximum independent set I we have | I ∩ S | ≥ d. We show that both problems are polynomial-time solvable in the class of co-comparability graphs by reducing them to the well-known Vertex Cut problem. Our results generalise a result of Chang et al. (2001) and a recent result of Hoang et al. (2023). [ABSTRACT FROM AUTHOR]

Let C k (n) denote the family of all connected graphs of order n with chromatic number k. In this paper we show that the conjecture proposed by Tomescu which if x ≥ k ≥ 4 and G ∈ C k (n) , then P (G , x) ≤ (x) k (x - 1) n - k holds under the additional condition that G has an independent cut-set T of size at most 2 such that the number of components in G \ T is equal to the independence number of G. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected connected graph, Tn,α be the set of trees with independence number α and order n. In this paper, we discuss the maximum reciprocal degree distance of trees in Tn,α and characterize the unique corresponding extremal graph. [ABSTRACT FROM AUTHOR]

For a positive integer k, a subset S of vertices of a graph G is k-independent if each vertex in S has at most k − 1 neighbors in S. We consider k-independent sets in two graph products: Cartesian and complementary prism. We show that the problem of determining k-independence remains NP-complete even for Cartesian products and complementary prisms. Furthermore, we present results on k-independence in the Cartesian product of two paths, known as grid graphs. [ABSTRACT FROM AUTHOR]

We estimate the likely values of the chromatic and independence numbers of the random r-uniform d-regular hypergraph on n vertices for fixed r, large fixed d, and n → ∞. [ABSTRACT FROM AUTHOR]

The cyclic graph Γ (S) of a semigroup S is the simple undirected graph whose vertex set is S and two vertices x , y are adjacent if the subsemigroup generated by x and y is monogenic. In this paper, we determine the clique number of Γ (S) for an arbitrary semigroup S. Further, we obtain the independence number of Γ (S) if S is a finite monogenic semigroup. At the final part of this paper, we give bounds for independence number of Γ (S) if S is a semigroup of bounded exponent and we also characterize the semigroups attaining the bounds. [ABSTRACT FROM AUTHOR]

The atom-bond sum-connectivity (ABS) index of a graph GG with edges e1,…,em{e}_{1},\ldots ,{e}_{m} is the sum of the numbers 1−2(dei+2)−1\sqrt{1-2{\left({d}_{{e}_{i}}+2)}^{-1}} over 1≤i≤m1\le i\le m, where dei{d}_{{e}_{i}} is the number of edges adjacent to ei{e}_{i}. In this article, we study the maximum values of the ABS index over graphs with given parameters. More specifically, we determine the maximum ABS index of connected graphs of a given order with a fixed (i) minimum degree, (ii) maximum degree, (iii) chromatic number, (iv) independence number, or (v) number of pendent vertices. We also characterize the graphs attaining the maximum ABS values in all of these classes.

AbstractA graph G is an integral sum graph (sum graph) if its vertices can be labeled with distinct integers (positive integers) so that e = uv is an edge of G if and only if the sum of the labels on vertices u and v is also a label in G. A graph G is perfect if the chromatic number of each of its induced subgraphs is equal to the clique number of the same. A simple graph G is of class 1 if its edge chromatic number and maximum degree are same. In this paper, we prove that integral sum graphs Gn, [Formula: see text] and [Formula: see text] over the label sets [Formula: see text] and [Formula: see text], respectively, are perfect graphs as well as of class 1 for [Formula: see text]. We also obtain a few structural properties of these graphs.

Let G n , α be the set of all connected graphs of order n with independence number α. A graph is called the Q -minimizer graph (A -minimizer graph) if it attains the minimum signless Laplacian spectral radius (adjacency spectral radius) over all graphs in G n , α. In this paper, we first show that the Q -minimizer graph must be a tree for α ≥ ⌈ n 2 ⌉ , and then we derive seven propositions about the Q -minimizer graph. Moreover, when n − α is a constant, the structure of the Q -minimizer graph is characterized. The method of getting Q -minimizer graph in this paper is different from that of getting A -minimizer graph. As applications, we determine the Q -minimizer graphs for α = n − 1 , n − 2 , n − 3 and n − 4 , respectively. The results of α = n − 1 , n − 2 , n − 3 are consistent with that in Li and Shu (2010) [15] and the result of α = n − 4 is new. Interestingly, the Q -minimizer graph in G n , n − 4 is unique, which is exactly one of the A -minimizer graphs in G n , n − 4. [ABSTRACT FROM AUTHOR]

We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter π by at least d? We show that this problem is NP-hard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed d = 1 and when restricted to chordal graphs. We give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy for H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard in (C 3 + P 1) -free graphs even for fixed d = 1 . When the operation is edge deletion and the parameter is the chromatic number, we determine the computational complexity of the associated problem for cographs and complete multipartite graphs. Our results answer several open questions stated in Diner et al. (Theor Comput Sci 746:49–72, 2012, https://doi.org/10.1016/j.tcs.2018.06.023). [ABSTRACT FROM AUTHOR]

The concept of k -independent set, introduced by Fink and Jacobson in 1986, is a natural generalization of classical independence set. A k -independent set is a set of vertices whose induced subgraph has maximum degree at most k. The k -independence number of G , denoted by α k (G) , is defined as the maximum cardinality of a k -independent set of G. As a natural counterpart of the k -independence number, we introduced the concept of k -edge-independence number. An edge set M in E (G) is called k -edge-independent if the maximum degree of the subgraph induced by the edges in M is less or equal to k. The k -edge-independence number, denoted β k (G) , is defined as the maximum cardinality of a k -edge-independent set. In this paper, we study the Nordhaus–Gaddum-type results for the parameter α k (G) and β k (G). We obtain sharp upper and lower bounds of α k (G) + α r (G ¯) , α k (G) ⋅ α r (G ¯) , β k (G) + β r (G ¯) and β k (G) ⋅ β r (G ¯) for a graph G of order n. Some graph classes attaining these bounds are also given. [ABSTRACT FROM AUTHOR]

In this paper, we determine the graphs which have the minimal spectral radius among all the connected graphs of order n and the independence number ⌈ n 2 ⌉ - 1. [ABSTRACT FROM AUTHOR]

A twirling channel is a quantum channel induced by a continuous unitary representation π = ∑ i ⊕ m i π i on a compact group G , where π i are inequivalent irreducible representations. Motivated by a recent work [ 8 ] on minimal mixed unitary rank of Φ π , we explore the connections of the independence number, zero-error capacity, quantum codes, orthogonality index and phase retrievability of the quantum channel Φ π with the irreducible representation multiplicities m i and the irreducible representation dimensions dim H π i . In particular, we show that the independence number of Φ π is the sum of the multiplicities, the orthogonal index of Φ π is exactly the sum of those representation dimensions, and the zero-error capacity is equal to log (∑ i = 1 d m i ). We also present a lower bound for the phase retrievability in terms of the minimal length of phase retrievable frames for ℂ n [ABSTRACT FROM AUTHOR]

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]

Consider a graph on the non-singular matrices over a finite field, in which two distinct non-singular matrices are joined by an edge whenever their sum is singular. We prove an upper bound for the independence number of this graph. As a consequence, we obtain a lower bound for its chromatic number that significantly improves a previous result of Tomon. [ABSTRACT FROM AUTHOR]

Let $ m_GI $ m G I denote the number of Laplacian eigenvalues of a graph G in an interval I and let $ \alpha (G) $ α (G) denote the independence number of G. In this paper, we determine the classes of graphs that satisfy the condition $ m_G[0,n-\alpha (G)]=\alpha (G) $ m G [ 0 , n − α (G) ] = α (G) when $ \alpha (G)= 2 $ α (G) = 2 and $ \alpha (G)= n-2 $ α (G) = n − 2 , where n is the order of G. When $ \alpha (G)=2 $ α (G) = 2 , $ G \cong K_1 \nabla K_{n-m} \nabla K_{m-1} $ G ≅ K 1 ∇ K n − m ∇ K m − 1 for some $ m \geq 2 $ m ≥ 2. When $ \alpha (G)=n-2 $ α (G) = n − 2 , there are two types of graphs $ B(p,q,r) $ B (p , q , r) and $ B'(p,q,r) $ B ′ (p , q , r) of order n = p + q + r + 2, which we call the binary star graphs. Also, we show that the binary star graphs with p = r are determined by their Laplacian spectra. [ABSTRACT FROM AUTHOR]

Let G$$ G $$ be an n$$ n $$‐vertex graph, where δ(G)≥δn$$ \delta (G)\ge \delta n $$ for some δ:=δ(n)$$ \delta := \delta (n) $$. A result of Bohman, Frieze and Martin from 2003 asserts that if α(G)=Oδ2n$$ \alpha (G)=O\left({\delta}^2n\right) $$, then perturbing G$$ G $$ via the addition of ωlog(1/δ)δ3$$ \omega \left(\frac{\log \left(1/\delta \right)}{\delta^3}\right) $$ random edges, a.a.s. yields a Hamiltonian graph. We prove several improvements and extensions of the aforementioned result. In particular, keeping the bound on α(G)$$ \alpha (G) $$ as above and allowing for δ=Ω(n−1/3)$$ \delta =\Omega \left({n}^{-1/3}\right) $$, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a pancyclic graph. Moreover, we prove similar results for sparser graphs, and assuming the correctness of Chvátal's toughness conjecture, we handle graphs having larger independent sets. Finally, under milder conditions, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a graph containing an almost spanning cycle. [ABSTRACT FROM AUTHOR]

Let (P , ≤) be an atomic poset with the least element 0. The complement of the intersection graph of ideals of P , denoted by Γ (P) , is defined to be a graph whose vertices are all non-trivial ideals of P and two distinct vertices I and J are adjacent if and only if I ∩ J = { 0 }. In this paper, we consider the complement of the intersection graph of ideals of a poset. We prove that Γ (P) is totally disconnected or diam (Γ (P) \) ∈ { 1 , 2 , 3 } , where is the set of all isolated vertices of Γ (P). We show that g r (Γ (P)) ∈ { 3 , 4 , ∞ }. Also, we characterize all posets whose complement of the intersection graph is forest, unicyclic or complete r -partite graph. Among other results, we prove that Γ (P) is weakly perfect; and it is perfect if and only if | Atom (P) | ≤ 4. Finally, we show that Γ (P) is class 1 , where P = Atom (P) ∪ { 0 }. [ABSTRACT FROM AUTHOR]

In this paper, we prove that every simple connected graph with α > n 2 has 1 as a normalized Laplacian eigenvalue with multiplicity at least 2 α − n , where n and α are the order and the independence number of the graph, respectively. Then we investigate graphs with α ≤ n 2 and having or not having 1 as a normalized Laplacian eigenvalue. [ABSTRACT FROM AUTHOR]

In this paper, we give a class of graphs that do not admit disjoint maximum and maximal independent (MMI) sets. The concept of inverse independence was introduced by Bhat and Bhat in [Inverse independence number of a graph, Int. J. Comput. Appl. 42(5) (2012) 9–13]. Let A be a α -set in G. An independent set D ⊂ V (G) − A is called an inverse independent set with respect to A. The inverse independence number α − 1 (G) is the size of the largest inverse independent set in G. Bhat and Bhat gave few bounds on the independence number of a graph, we continue the study by giving some new bounds and exact value for particular classes of graphs: spider tree, the rooted product and Cartesian product of two particular graphs. [ABSTRACT FROM AUTHOR]

Let G be a finite group and A G be the automorphism group of G (i.e. Aut (G)). We associated a bipartite graph, denoted by Γ G , to G and its automorphism group Aut (G) as follows: two parts of the vertex set are G \ L (G , Z (G)) and A G \ Aut c (G) , where L (G , Z (G)) is the set of elements g ∈ G such that g − 1 α (g) ∈ Z (G) for all α ∈ A G and Aut c (G) is the set of automorphisms β ∈ A G such that g − 1 β (g) ∈ Z (G) for all g ∈ G. Two vertices g ∈ G \ L (G , Z (G)) and α ∈ A G \ Aut c (G) are adjacent if and only if g − 1 α (g) ∉ Z (G). In this paper, we investigate some fundamental properties of Γ G such as connectivity, diameter, girth, Hamiltonian, independence and dominating numbers. Moreover, planarity and outer planarity of the graph are studied. [ABSTRACT FROM AUTHOR]

A prime labeling of a simple undirected graph G is to assign unique integer labels from the set {1,2,...,|V(G)|} to each vertex such that any two adjacent vertices in the graph have labels that are relatively prime. Studying prime labeling in graphs can help us understand the structure and properties of graphs and prime labeling has potential applications in cryptography and network security. In this paper we investigate when some graphs that are constructed from wheels are prime graphs.

A graph $G$ is called semi square stable if $\alpha (G^{2})=i(G)$ where $%\alpha (G^{2})$ is the independence number of $G^{2}$ and $i(G)$ is the independent dominating number of $G$. A subset $S$ of the vertex set of a graph $G$ is an efficient dominating set if $S$ is an independent set and every vertex of $G$ is either in $S$ or adjacent to exactly one vertex of $%S. $In this paper, we show that every square stable graph has an efficient dominating set and if a graph has an efficient dominating set, then it is semi square stable. We characterize when the join and the corona product of two disjoint graphs are semi square sable graphs and when they have efficient dominating sets.

Consider a simple graph $ \Gamma = (V(\Gamma), E(\Gamma)) $ with $ n $ vertices and $ m $ edges. Let $ P $ be a subset of $ V(\Gamma) $ and $ B(P) $ the set of neighbors of $ P $ in $ V(\Gamma)\backslash P $. In the study of graphs, the concept of differential refers to a measure of how much the number of edges leaving a set of vertices exceeds the size of that set. Specifically, given a subset $ P $ of vertices, the differential of $ P $, denoted by $ \partial(P) $, is defined as $ |B(P)|-|P| $. The differential of $ \Gamma $, denoted by $ \partial(\Gamma) $, is then defined as the maximum differential over all possible subsets of $ V(\Gamma) $. Additionally, the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ is defined as the graph obtained from $ \Gamma $ by inserting a new vertex on each edge of $ \Gamma $. In this paper, we present results for the differential of graphs on the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ where some of these show exact values of $ \partial({{\mathcal{S}}({\Gamma})}) $ if $ \Gamma $ belongs to a classical family of graphs. We obtain bounds for $ \partial({{\mathcal{S}}({\Gamma})}) $ involving invariants of a graph such as order $ n $, size $ m $ and maximum degree $ \Delta $, and we study the realizability of the graph $ \Gamma $ for any value of $ \partial({{\mathcal{S}}({\Gamma})}) $ in the interval $ \left[n-2, \frac{n(n-1)}{2}-n+2\right] $. Moreover, we give a characterization for $ \partial({{\mathcal{S}}({\Gamma})}) $ using the notion of edge star packing.

We consider a family of distance graphs in R n and find its independence numbers in some cases. Define the graph J ± (n , k , t) in the following way: the vertex set consists of all vectors from { - 1 , 0 , 1 } n with exactly k nonzero coordinates; edges connect the pairs of vertices with scalar product t. We find the independence number of J ± (n , k , t) for an odd negative t and n > n 0 (k , t) . [ABSTRACT FROM AUTHOR]

The pairwise balanced designs (PBD's) is a pair (P;B), where P is a finite set of v points and B is a family of subsets of P, called blocks such that every two distinct points in P appear in exactly one block. Let α(G) = α and β(G) = β be the vertex covering and independence number of a graph G = (V;E) with the minimum and maximum cardinality of such sets are denoted by α-sets and β-sets of G, respectively (or, simply (α; β)-sets). In this paper, we obtain the total number of (α; β)-sets in different jump sizes of some circulant graphs apart from strongly regular graphs which are the blocks of PBD. [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]

The independence number of a square matrix A , denoted by α (A) , is the maximum order of its principal zero submatrices. Given any integer n , let S n + be the set of n × n nonnegative symmetric matrices with zero diagonal. We characterize the linear maps on S n + preserving the independence number of all matrices in S n +. [ABSTRACT FROM AUTHOR]

For k ≥ 1 , the k -independence number α k of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α (= α 1) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for α k , showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials. [ABSTRACT FROM AUTHOR]

We propose new bounds on the domination number and on the independence number of a graph and show that our bounds compare favorably to recent ones. Our bounds are obtained by using the Bhatia-Davis inequality linking the variance, the expected value, the minimum, and the maximum of a random variable with bounded distribution. [ABSTRACT FROM AUTHOR]

The k-token graph Tk(G) is the graph whose vertices are the k-subsets of vertices of a graph G, with two vertices of Tk(G) adjacent if their symmetric difference is an edge of G. We explore when Tk(G) is a well-covered graph, that is, when all of its maximal independent sets have the same cardinality. For bipartite graphs G, we classify when Tk(G) is well-covered. For an arbitrary graph G, we show that if T2(G) is well-covered, then the girth of G is at most four. We include upper and lower bounds on the independence number of Tk(G), and provide some families of well-covered token graphs. [ABSTRACT FROM AUTHOR]

Let D(G) and A(G), respectively, be the diagonal matrix of vertex de- grees and the adjacency matrix of a connected graph G. The generalized adjacency matrix of G is defined as Aα(G) = αD(G) + (1 − α)A(G), α ∈ [0, 1]. The spread of the generalized adjacency matrix, denoted by S(Aα(G)), is defined as the difference of the largest and smallest eigenvalues of Aα(G). The spread S(Q(G)) of Q(G), the signless Laplacian matrix of G and S(A(G)) of A(G) are similarly defined. In this paper, we establish the relationships between S(Aα(G)), S(Q(G)) and S(A(G)). Further, we find bounds for S(Aα(G)) involving different parameters of G. Also, we obtain lower bounds for S(Aα(G)) in terms of the clique number and independence number of G, and we characterize the extremal graphs in some cases. [ABSTRACT FROM AUTHOR]

In view of this paper, we have defined Rough Co-zero divisor graph G (Z ∗ (J)) of a rough semiring (T , Δ , ∇) for a given approximation space I = (U , R) where U is nonempty finite set of objects and R is an arbitrary equivalence relation on U. It is proved that the Rough Co-zero divisor graph and the subgraph of Rough Ideal-based rough edge Cayley graph G (T ∗ (J)) are complement to each other. Also the Clique number and Independence number of G (T ∗ (J)) and G (Z ∗ (J)) are obtained. The developed concepts are illustrated with suitable examples. A sentiment analysis is also made using G (T ∗ (J)) for a Twitter data. [ABSTRACT FROM AUTHOR]

For a given graph H , the independence number α (H) of H is the size of the maximum independent set of V (H). Finding the maximum independent set in a graph is NP-hard. Another version of the independence number is defined as the size of the maximum-induced forest of H , and called the forest number of H , and denoted by f (H). Finding f (H) is also an NP-hard problem. Suppose that H = (V (H) , E (H)) is a graph, and is a family of graphs, a graph H has a -free k -coloring if there exists a decomposition of V (H) into sets V i , i = 1 , 2 , ... , k , so that G ⊈ H [ V i ] for each i , and each G ∈ . S ⊆ V (H) is G -free, if the subgraph of H induced by S is G -free, i.e., it contains no copy of G. Finding a maximum subset S of H , such that H [ S ] is a G -free graph is a very hard problem as well. In this paper, we study the generalized version of the independence number of a graph. Also, we give some bounds about the size of the maximum G -free subset of graphs as another purpose of this paper. [ABSTRACT FROM AUTHOR]

Given a graph G, the adjacency matrix and degree diagonal matrix of G are denoted by A(G) and D(G), respectively. In 2017, Nikiforov[24] proposed the Aα-matrix: Aα(G) = αD(G) + (1 − α)A(G), where α ∈ [0, 1]. The largest eigenvalue of this novel matrix is called the Aα-index of G. In this paper, we characterize the graphs with minimum Aα-index among n-vertex graphs with independence number i for α ∈ [0, 1), where i = 1 , ⌊ n 2 ⌋ , ⌈ n 2 ⌉ , ⌊ n 2 ⌋ + 1 , n − 3 , n − 2 , n − 1 , whereas for i = 2 we consider the same problem for α ∈ [ 0 , 3 4 ] . Furthermore, we determine the unique graph (resp. tree) on n vertices with given independence number having the maximum Aα-index with α ∈ [0, 1), whereas for the n-vertex bipartite graphs with given independence number, we characterize the unique graph having the maximum Aα-index with α ∈ [ 1 2 , 1) . [ABSTRACT FROM AUTHOR]