Search

The Hoffman ratio bound, Lovász theta function, and Schrijver theta function are classical upper bounds for the independence number of graphs, which are useful in graph theory, extremal combinatorics, and information theory. By using generalized inverses and eigenvalues of graph matrices, we give bounds for independence sets and the independence number of graphs. Our bounds unify the Lovász theta function, Schrijver theta function, and Hoffman-type bounds, and we obtain the necessary and sufficient conditions of graphs attaining these bounds. Our work leads to some simple structural and spectral conditions for determining a maximum independent set, the independence number, the Shannon capacity, and the Lovász theta function of a graph. [ABSTRACT FROM AUTHOR]

In a graph G = (V,E)(not necessarily connected), an independent set S ⊆ V is said to be an outer-connected independent set if ω(G − S) ≤ ω(G), where ω(G) is the number of components in G. The maximum cardinality of an outer connected independent set is called the outer-connected independence number and is denoted by Ioc(G). This concept was introduced in [I. Sahul Hamid, R. Gnanaprahasam and M. Fatima Mary, Outer connected independence in graphs, Discrete Math. Algor. Appl. 7(3) (2015), Article ID: 1550039, 11 pp., doi: 10.1142/S1793830915500391], and as a continuation of this work, the effect of Ioc on edge removal was reported in [M. Fatima Mary, A. Anitha and I. Sahul Hamid, Edge-criticality in unicyclic graphs upon outer connected independence, Adv. Appl. Math. Sci. 21(8) (2022) 4221–4238] and [I. Sahul Hamid and M. Fatima Mary, Criticality of outer connected independence upon edge removal, Electron. Notes Discr. Math. 63 (2017) 361–369]. This paper presents a further study of the critical edges upon Ioc in trees. [ABSTRACT FROM AUTHOR]

In this paper, we use the double counting method to find some upper bounds for the independence number of a simple graph in terms of its order, size and maximum degree. Moreover, we determine extremal graphs attaining equality in upper bounds. In addition, some lower bounds for the energy of graphs in terms of their size and maximum degree and the number of odd cycle, are determined. [ABSTRACT FROM AUTHOR]

A P ≥ k -factor is a spanning subgraph H of G whose components are paths of order at least k. A graph G is P ≥ k -factor uniform if for arbitrary e 1 , e 2 ∈ E (G) with e 1 ≠ e 2 , G has a P ≥ k -factor containing e 1 and avoiding e 2. Liu first put forward the concept of (P ≥ k , n) -critical uniform graph, that is, a graph G is called (P ≥ k , n) -critical uniform if the graph G − V ′ is P ≥ k -factor uniform for any V ′ ⊆ V (G) with | V ′ | = n. In this paper, two new results on (P ≥ k , n) -critical uniform graphs (k = 2 , 3) in terms of independence number and minimum degree are presented. Furthermore, we show the sharpness of the main results in this paper by structuring special counterexamples. [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]

The stable equivalent set is a finite collection of disjoint vertex subsets for a connected graph G = (V (G),E(G)) such that each set induces the same maximal independent set of G and their union equals V (G). The stable equivalence number is the maximum cardinality of the stable equivalent set S, and it is represented by the symbol Sα(G). In order to analyze the fault-tolerant and local metric dimensions of the intersection graph of gamma sets in the zero-divisor graph, IΓ(R), the stable equivalent set of IΓ(R) was used. [ABSTRACT FROM AUTHOR]

Closeness is a measure that quantifies how quickly information can spread from a given node to all other nodes in the network, reflecting the efficiency of communication within the network by indicating how close a node is to all other nodes. For a graph G, the subset S of vertices of V (G) is called vertex cut of G if the graph G − S becomes disconnected. The minimum cardinality of S for which G − S is either disconnected or contains precisely one vertex is called connectivity of G. A graph is called k-connected if it stays connected even when any set of fewer than k vertices is removed. In communication networks, a k-connected graph improves network reliability; even if up to k − 1 nodes fail, the network remains operational, maintaining connectivity between devices. This paper aims to study the concept of closeness within n-vertex graphs with fixed connectivity. First, we identify the graphs that maximize the closeness among all graphs of order n with fixed connectivity k. Then, we determine the graphs that achieve the maximum closeness within all k-connected graphs of order n, given specific fixed parameters such as diameter, independence number, and minimum degree. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study the power graph of a semigroup. We obtain sufficient and necessary conditions for the independence number of the power graph of an (IC) abundant semigroups (superabundant semigroups) to be finite.

‎In this paper, we use the double counting method to find some upper bounds for the independence number of a simple graph in terms of its order, size and maximum degree. Moreover, we determine extremal graphs attaining equality in upper bounds. In addition, some lower bounds for the energy of graphs in terms of their size and maximum degree and the number of odd cycle, are determined.

In the context of a simple undirected graph GG, a kk-prime labeling refers to assigning distinct integers from the set {k,k+1,…,∣V(G)∣+k−1}\left\{k,k+1,\ldots ,| V\left(G)| +k-1\right\} to its vertices, such that adjacent vertices in GG are labeled with numbers that are relatively prime to each other. If GG has a kk-prime labeling, we say that GG is a kk-prime graph (k-PG). In this article, we characterize when a graph up to order 6 is a k-PG and characterize when a graph of order 7 is a k-PG whenever kk and k+1k+1 are not divisible by 5. Also, we find a lower bound for the independence number of a k-PG. Finally, we study when a cycle is a k-PG.

A distinguishing coloring of a simple graph $G$ is a vertex coloring of $G$ which is preserved only by the identity automorphism of $G$. In other words, this coloring ``breaks'' all symmetries of $G$. The distinguishing number $D(G)$ of a graph $G$ is defined to be the smallest number of colors in a distinguishing coloring of $G$. This concept of “symmetry breaking” was first proposed by Babai in 1977 and after the publication of a seminal paper by Albertson in 1996, it attracted the attention of many mathematicians. In this paper, along with studying some relations between $D(G)$ and some other important graph parameters, we introduce the concept of a $(D,\alpha)$-ordinary graph which displays the comparison between $D(G)$ and the independence number $\alpha(G)$. Then we consider the classification of $(D,\alpha)$-ordinary graphs in various families of graphs such as forests, cycles, generalized Johnson graphs, Cartesian products of graphs and line graphs of connected claw-free graphs. We also propose some conjectures and discuss about some future research directions in this topic.

Let [Formula: see text] be the principal eigenvector corresponding to the spectral radius [Formula: see text] of a graph G of order n. In this paper, we find some bounds on the ratio of the maximal component [Formula: see text] to the minimal component [Formula: see text] of the principal eigenvector X in terms of the graph parameters such as the independence number [Formula: see text], the minimum vertex cover number of the vertex [Formula: see text] and the chromatic number [Formula: see text]. Also, we present some bounds on the extremal component [Formula: see text] of the principal eigenvector X. An upper bound of the spectral radius [Formula: see text] of G in terms of the minimum vertex cover number [Formula: see text] and order of the graph n is also introduced in this paper.

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]

For a graph G, let κ(G) and α(G) be the connectivity and independence number of G, respectively. A well-known theorem of Chv'atal and Erd˝os says that if G is a graph of order n with κ(G) > α(G), then G is Hamilton-connected. In this paper, we prove the following Chv'atal-Erd˝os type theorem: if G is a k-connected graph, k ≥ 2, of order n with independence number α, then each pair of distinct vertices of G is joined by a Hamiltonian path or a path of length at least (k - 1)max n+-k, n+2-2k+1. Examples show that this result is best possible. We also strength it in terms of subgraphs. [ABSTRACT FROM AUTHOR]

A prime labeling of a graph G is a map from the vertex set of G, V(G), to the set {1, 2, ..., |V(G)|} such that any two adjacent vertices in the graph G have labels that are relatively prime. In this paper, we discuss when the disjoint union of some graphs is a prime graph. [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]

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]

A spanning subgraph H of a graph G is called a path-factor if every component of H is a path. Wang and Zhang [RAIRO:RO 57 (2023) 2231–2237] conjectured that a connected graph G with δ(G) ≥ 5 contains a {P2, P5}-factor if δ(G)≥3α(G)−14 δ (G) ≥ 3 α (G) − 1 4 $ \delta{(G)}\geq\frac{3\alpha{(G)-1}}4$ , where δ(G) and α(G) denote the minimum degree and independence number of G, respectively. We show that the conjecture is true except G≅X ∨ 7K3, where X is a spanning subgraph of K3. Furthermore, we give two degree conditions for the existence of {P2, P5}-factors, one of which is a stronger version of Wang's another conjecture. We also show the degree conditions are best possible. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n and L (G) ≡ L 1 (G) its line graph. Then, the iterated line graph of G is defined recursively as L 2 (G) ≡ L (L (G)), L 3 (G) ≡ L (L 2 (G)), …, L k (G) ≡ L (L k − 1 (G)). The energy E (G) is the sum of absolute values of the eigenvalues of G. In this paper, it is derived a sharp upper bound for the energy of the line graph of a connected graph G of order n and independence number not less than α where 1 ≤ α ≤ n − 2. This bound is attained, if and only if, G is isomorphic to the complete split graphs S K n, α. It is also determined a lower bound for the energy of the line graph of a graph G of order n and independence number α. For 1 ≤ α ≤ n − 1 and H = (n − α ⌊ n α ⌋) K ⌊ n α ⌋ + 1 ⋃ (α + α ⌊ n α ⌋ − n) K ⌊ n α ⌋, the equality holds, if and only if G ≅ H. As a consequence, families of hyperenergetic graphs are determined. Also, a lower bound for the energy of the iterated line of a graph G of order n and independence number α is given and, for 1 ≤ α ≤ n − 1, the equality holds, if and only if, G ≅ α K ⌊ n α ⌋. Additionally, an upper bound for the incidence energy of connected graphs G of order n and independence number not less than α is presented. Moreover, an upper bound on the Laplacian energy-like of the complement G ‾ of G is presented. For 1 ≤ α ≤ n − 1, the bound is attained, if and only if, G ≅ H. Finally, a Nordhaus-Gaddum type relation is given. [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]

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]

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]

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]

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]

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]

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]

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]

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.

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]

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]

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

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.