Search

Graph properties’ computation is widely used in science. Some algorithms for specific graphs help us compute properties like girth, clique number, and independent number. Nevertheless, processing time would be increased by the growth of the number of graph vertices. This paper suggests machine learning methods for computing a given graph’s girth, maximum clique number, and maximum independent set number. We leveraged random graph generation methods to collect many graph instances. Next, we present 14 features used for the training and testing while classifying or predicting those properties. The experimental results on the collected dataset offer accuracies of 90.51%, 91.61%, and 99.99% for binary classification and correlation coefficients of 0.9703, 0.8757, and 0.992 for value prediction for maximum clique number, girth, and maximum independent set number, respectively. [ABSTRACT FROM AUTHOR]

We use P t and C t to denote a path and a cycle on t vertices, respectively. A diamond is a graph obtained from two triangles that share exactly one edge. A kite is a graph that consists of a diamond and another vertex adjacent to a vertex of degree 2 of the diamond. A gem is a graph that consists of a P 4 plus a vertex adjacent to all vertices of the P 4. Choudum et al. (2021) proved that every ( P 7 , C 7 , C 4 , gem)-free graph has either a clique cutset or a vertex whose neighbors is the union of two cliques unless it is a clique blowup of the Petersen graph, and every non-Petersen ( P 7 , C 7 , C 4 , diamond)-free graph has either a clique cutset or has a vertex of degree at most max { 2 , ω (G) − 1 }. In this paper, we extend these two results respectively to ( P 7 , C 4 , gem)-free graphs and ( P 7 , C 4 , diamond)-free graphs. We also prove that if G is a ( P 7 , C 4 , kite)-free graph with δ (G) ≤ ω (G) and without clique cutsets, then there is an integer ℓ ≥ 0 such that G = K ℓ + H , where H is either the Petersen graph or a well-defined graph F. This implies a polynomial algorithm which can determine the chromatic number of ( P 7 , C 4 , diamond)-free graphs, color ( P 7 , C 4 , kite)-free graphs G with (ω (G) + 1) colors, and color ( P 7 , C 4 , gem)-free graphs G with (2 ω (G) − 1) colors. [ABSTRACT FROM AUTHOR]

Hocquard, Kim, and Pierron constructed, for every even integer D≥2 $D\ge 2$, a 2‐degenerate graph GD ${G}_{D}$ with maximum degree D $D$ such that ω(GD2)=52D $\omega ({G}_{D}^{2})=\frac{5}{2}D$. We prove for (a) all 2‐degenerate graphs G $G$ and (b) all graphs G $G$ with mad(G)<4 $\text{mad}(G)\lt 4$, upper bounds on the clique number ω(G2) $\omega ({G}^{2})$ of G2 ${G}^{2}$ that match the lower bound given by this construction, up to small additive constants. We show that if G $G$ is 2‐degenerate with maximum degree D $D$, then ω(G2)≤52D+72 $\omega ({G}^{2})\le \frac{5}{2}D+72$ (with ω(G2)≤52D+60 $\omega ({G}^{2})\le \frac{5}{2}D+60$ when D $D$ is sufficiently large). And if G $G$ has mad(G)<4 $\text{mad}(G)\lt 4$ and maximum degree D $D$, then ω(G2)≤52D+532 $\omega ({G}^{2})\le \frac{5}{2}D+532$. Thus, the construction of Hocquard et al. is essentially the best possible. Our proofs introduce a "token passing" technique to derive crucial information about nonadjacencies in G $G$ of vertices that are adjacent in G2 ${G}^{2}$. This is a powerful technique for working with such graphs that has not previously appeared in the literature. [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]

The intersection non-simple graph, denoted by INS(G), of a finite abelian group G is an undirected graph whose vertex set is the collection of all proper non-trivial subgroups of G, and any two distinct vertices are adjacent if and only if their intersection is not a simple subgroup of G. We obtain some properties of INS(G) related to connectedness, completeness, degree, and girth. The concepts of bipartiteness, triangle-free, cluster, claw-free and cograph are taken into consideration. We also investigate the clique number, independence number, domination number, and planarity of INS(G). [ABSTRACT FROM AUTHOR]

It is known that the so-called Beck's conjecture, i.e. the equality of the finite clique and chromatic numbers of a zero-divisor graph, holds for partially ordered sets Halaš and Jukl (Discrete Math 309(13):4584–4589, 2009). In this paper we present a simple direct proof of this fact. Also, the case when the finiteness assumption of the clique number is omitted is investigated. We have shown that the conjecture fails in general and a bunch of counterexamples is presented. [ABSTRACT FROM AUTHOR]

The spectral radius ρ (G) of a graph G is the largest eigenvalue of the adjacency matrix of G. For a graph G with maximum degree Δ (G) , it is known that ρ (G) ≤ Δ (G) with equality when G is connected if and only if G is regular. So the quantity β (G) = Δ (G) - ρ (G) is a spectral measure of irregularity of G. In this paper, we identify the trees of order n ≥ 12 with the first 15 largest β -values, the unicyclic graphs of order n ≥ 17 with the first 16 largest β -values, as well as the bicyclic graphs of order n ≥ 30 with the first 11 largest β -values. We also determine the graphs with the largest β -values among all connected graphs with given order and clique number. [ABSTRACT FROM AUTHOR]

Let G be a graph. We use χ(G) and ω(G) to denote the chromatic number and clique number of G respectively. A P5 is a path on 5 vertices, and an HVN is a K4 together with one more vertex which is adjacent to exactly two vertices of K4. Combining with some known result, in this paper we show that if G is (P5, HVN)-free, then χ(G) ≤ max{min{16, ω(G) + 3}, ω(G) + 1}. This upper bound is almost sharp. [ABSTRACT FROM AUTHOR]

The computation of the clique number of a graph is a fundamental problem in graph theory, which has many applications in computational chemistry, bioinformatics, computer, and social networking. A subset [Formula: see text] of non-negative integers [Formula: see text] is called a numerical semigroup if it is a submonoid of [Formula: see text] and has a finite complement in [Formula: see text]. The graph associated with numerical semigroup [Formula: see text] is denoted by [Formula: see text] and is defined by the vertex set [Formula: see text] and the edge set [Formula: see text]. In this article, we compute the clique number and the minimum degree of those graphs, which can be associated with symmetric numerical semigroups of embedding dimension 2. Moreover, on this basis, we give some bounds for the atom-bond sum-connective index of graphs [Formula: see text] in terms of the harmonic index, the first Zagreb index, the sum-connectivity index, the maximum degree, the minimum degree, the chromatic number, and the clique number.

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.

Let R be a finite commutative ring with or without unity and Γe(R) be its extended zero-divisor graph with vertex set Z*(R) = Z(R)\{0} and two distinct vertices x, y are adjacent if and only if x.y = 0 or x + y ∈ Z*(R). In this paper, we characterize finite commutative rings whose extended zero-divisor graph have clique number 1 or 2. We completely characterize the rings of the form R ≅ R1 x R2, where R1 and R2 are local, having clique number 3, 4 or 5. Further we determine the rings of the form R ≅ R1 x R2 x R3, where R1, R2 and R3 are local rings, to have clique number equal to six. [ABSTRACT FROM AUTHOR]

The eccentricity of a vertex u in a graph G , denoted by ɛ G (u) , is the maximum distance from u to other vertices in G. We study extremal problems for the average eccentricity and the first and second Zagreb eccentricity indices, denoted by σ 0 (G) , σ 1 (G) , and σ 2 (G) , respectively. These are defined by σ 0 (G) = 1 | V (G) | ∑ u ∈ V (G) ɛ G (u) , σ 1 (G) = ∑ u ∈ V (G) ɛ G 2 (u) , and σ 2 (G) = ∑ u v ∈ E (G) ɛ G (u) ɛ G (v). We study lower and upper bounds on these parameters among n -vertex connected graphs with fixed diameter, chromatic number, clique number, or matching number. Most of the bounds are sharp, with the corresponding extremal graphs characterized. [ABSTRACT FROM AUTHOR]

Let G be a graph. We use χ (G) and ω (G) to denote the chromatic number and clique number of G, respectively. A P 5 is a path on 5 vertices, a C 5 is a cycle on 5 vertices, and a K 5 - e is obtained by removing one edge from K 5 . Chudnovsky and Sivaraman showed that χ (G) ≤ 2 ω (G) - 1 if G is ( P 5 , C 5) -free. In this paper, we show that every non-perfect (P 5 , C 5 , K 5 - e) -free graph is 5-colorable. [ABSTRACT FROM AUTHOR]

Let G be a finite group. The non-commuting graph of G is a simple graph Γ(G) whose vertices are elements of G\Z(G), where Z(G) is the center of G, and two distinct vertices a and b are joint by an edge if ab ≠ ba. In this paper, we study the non-commuting graph of the group U6n. The independent number, clique and chromatic numbers of the non-commuting graph of the group U6n, Γ(U6n), are determined. Additionally, the resolving polynomial, total eccentricity and independent polynomials of Γ(U6n) are computed. Finally, the detour and eccentric connectivity indices of Γ(U6n) are found. [ABSTRACT FROM AUTHOR]

Let h = ∏ i = 1 t p i s i be its decomposition into a product of powers of distinct primes, and ℤ h be the residue class ring modulo h. Let ℤ h n be the n -dimensional row vector space over ℤ h . A generalized Grassmann graph over ℤ h , denoted by G r (m , n , ℤ h) ( G r for short), has all m -subspaces of ℤ h n as its vertices, and two distinct vertices are adjacent if their intersection is of dimension > m − r , where 2 ≤ r ≤ m + 1 ≤ n. In this paper, we determine the clique number and geometric structures of maximum cliques of G r . As a result, we obtain the Erdős–Ko–Rado theorem for ℤ h n . [ABSTRACT FROM AUTHOR]

A d-dimensional annulus graph with radii R 1 and R 2 (here R 2 ≥ R 1 ≥ 0 ) is a graph embeddable in R d so that two vertices u and v form an edge if and only if their images in the embedding are at distance in the interval [ R 1 , R 2 ] . In this paper we show that the family A d (R 1 , R 2) of d-dimensional annulus graphs with radii R 1 and R 2 is uniquely characterised by R 2 / R 1 when this ratio is sufficiently large. Moreover, as a step towards a better understanding of the structure of A d (R 1 , R 2) , we show that sup G ∈ A d (R 1 , R 2) χ (G) / ω (G) is given by exp (O (d)) for all R 1 , R 2 satisfying R 2 ≥ R 1 > 0 and also exp (Ω (d)) if moreover R 2 / R 1 ≥ 1.2 . [ABSTRACT FROM AUTHOR]

The common divisor graph, Γ (X) , is a graph that has been defined on a set of positive integers X. Some properties of this graph have been studied in the cases when either X is the set of character degrees or the set of conjugacy class sizes of a group. This paper deals with several properties of a particular case of the common divisor graph, Γ (Z) , when Z is a multiset of positive integers that admits a decomposition Z = X Y , where X Y = { x y | x ∈ X , y ∈ Y } and 1 ∈ X and 1 ∈ Y . Our results can be applied for the graphs associated to character degrees and conjugacy classes of the direct product of two finite groups. [ABSTRACT FROM AUTHOR]

For any connected graph G = (V , E) and any function f on the positive integers set Z + , vertex-degree function index H f (G) is defined as the sum of f (d G (v)) over v ∈ V , where d G (v) is the degree of v in G. For any n , k ∈ Z + with n ≥ k , connected graphs with n vertices and clique number k form the set W n , k . In this paper, for any strictly concave and increasing function f on Z + , we determine the maximal and minimal values of H f (G) over G ∈ W n , k , and characterize the corresponding graphs G ∈ W n , k with the extremal values. We also get the maximum vertex-degree function index H f (G) , where f(x) is a strictly concave and decreasing function for x ≥ 1 . [ABSTRACT FROM AUTHOR]

In this paper. A new definition of discrete topological graph is introduced. Some properties of this graph are proved. If n > 2 are evaluated Gτ has no pendant vertex, not tree, also the value of the diameter and the minimum degree of Gτ . If n ≥ 2, Gτ has (2n − 3) complete bipartite induced subgraphs, Gτ is connected graph, simple graph, has no odd cycle, the clique number also proved, the value of the radius, the maximum degree and the chromatic number of Gτ have been studied. [ABSTRACT FROM AUTHOR]

A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach nongeometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random 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]

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.

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]

We determine the maximum possible number of edges of a graph with n vertices, matching number at most s and clique number at most k for all admissible values of the parameters. [ABSTRACT FROM AUTHOR]

We investigate two conjectured spectral graph theoretic strengthenings of Turán's theorem. Let μ 1 ≥ ... ≥ μ n denote the eigenvalues of a graph G with n vertices, m edges and clique number ω (G). The concise version of Turán's theorem is that n / (n − d) is a lower bound for the clique number ω (G) , where d is the average degree. Our first conjecture is that d can be replaced in this bound with s + , where s + is the sum of the squares of the positive eigenvalues. We prove this conjecture for triangle-free, weakly perfect and Kneser graphs and for almost all graphs. We have also used various software tools to search for a counter-example. Nikiforov proved a spectral version of Turán's theorem that μ 1 2 ≤ 2 m (ω (G) − 1) ω (G) , and Bollobás and Nikiforov conjectured that for G ≠ K n μ 1 2 + μ 2 2 ≤ 2 m (ω (G) − 1) ω (G). For our second conjecture, we propose that for all graphs (μ 1 2 + μ 2 2) in this inequality can be replaced by the sum of the squares of the ω (G) largest eigenvalues, provided they are positive. We prove the conjecture for weakly perfect, Kneser, and classes of strongly regular graphs. We also provide experimental evidence and describe how the bound can be applied. Liu and Ning [19] published a wide-ranging paper entitled "Unsolved Problems in spectral graph theory", and these two conjectures were placed second and fourth in their list of such problems. [ABSTRACT FROM AUTHOR]

In this paper, we investigate when symbolic and ordinary powers of the parity binomial edge ideal of a graph fail to be equal. It turns out that if I G is the parity binomial edge ideal of a graph G, then in each of the following cases the symbolic power I G (t) and the ordinary power I G t are not equal for some t: (i) the clique number of G is greater than 3; (ii) G has a net; or (iii) G has a PT as an induced subgraph. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity and Nil(R) be the set of all nilpotent elements of R. The nil clean graph of R, denoted by N.G(R), is a graph whose vertices are all nonzero nil clean elements of R and two distinct vertices x and y are adjacent if and only if xy ∈Nil(R) or x − y ∈Nil(R). In this paper, we focus on N.G2(R), the subgraph of N.G(R) induced by the set N.G2(R) = {(e,n):0, 1≠e ∈Id(R)andn ∈Nil(R)}. It is observed that N.G2(R) has a crucial role in N.G(R). We prove that N.G2(R) is connected with diam(N.G2(R)) ≤ 3 and gr(N.G2(R)) ∈{3,∞}. We investigate also the interplay between the ring-theoretic properties of R and the graph-theoretic properties of N.G2(R). Moreover, the clique number and the chromatic number of N.G2(R) for some classes of rings are determined. [ABSTRACT FROM AUTHOR]

Let P n and K n denote the induced path and complete graph on n vertices, respectively. The kite is the graph obtained from a P 4 by adding a vertex and making it adjacent to all vertices in the P 4 except one vertex with degree 1. A graph is (P 5 , kite)-free if it has no induced subgraph isomorphic to a P 5 or a kite. For a graph G , the chromatic number of G (denoted by χ (G)) is the minimum number of colors needed to color the vertices of G such that no two adjacent vertices receive the same color, and the clique number of G is the size of a largest clique in G. Here, we are interested in coloring the class of (P 5 , kite)-free graphs with small clique number. It is known that every (P 5 , kite, K 3)-free graph G satisfies χ (G) ≤ 3 , every (P 5 , kite, K 4)-free graph G satisfies χ (G) ≤ 4 , and that every (P 5 , kite, K 5)-free graph G satisfies χ (G) ≤ 6. In this paper, we show the following: • Every (P 5 , kite, K 6)-free graph G satisfies χ (G) ≤ 7. • Every (P 5 , kite, K 7)-free graph G satisfies χ (G) ≤ 9. We also give examples to show that the above bounds are tight. Based on these partial results and some other examples, we conjecture that every (P 5 , kite)-free graph G satisfies χ (G) ≤ ⌊ 3 ω (G) 2 ⌋ , and that the bound is tight. [ABSTRACT FROM AUTHOR]

The atom-bond sum-connectivity index (A B S index) of a graph G = (V , E) is defined as A B S (G) = ∑ ξ ζ ∈ E (G) d ξ + d ζ − 2 d ξ + d ζ , where d ξ represents the degree of vertex ξ ∈ V. By using A B S index, the heat of formation of octane and heptane can be accurately predicted. The approximate value of the range for topological indices via certain parameters of molecular graphs is a major source of information in studying the molecular structure. In this paper, we determine the maximum values of A B S index in the collection of graphs which was provided with some predetermined parameters containing clique number, chromatic number etc., furthermore, the relevant extremal graphs were depicted. [ABSTRACT FROM AUTHOR]

For a graph G $G$, let χ(G) $\chi (G)$ (ω(G) $\omega (G)$) denote its chromatic (clique) number. A P2+P3 ${P}_{2}+{P}_{3}$ is the graph obtained by taking the disjoint union of a two‐vertex path P2 ${P}_{2}$ and a three‐vertex path P3 ${P}_{3}$. A P2+P3¯ $\bar{{P}_{2}+{P}_{3}}$ is the complement graph of a P2+P3 ${P}_{2}+{P}_{3}$. In this paper, we study the class of (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs and show that every such graph G $G$ with ω(G)≥3 $\omega (G)\ge 3$ satisfies χ(G)≤max{ω(G)+3,⌊32ω(G)⌋−1} $\chi (G)\le \max \{\omega (G)+3,\lfloor \phantom{\rule[-0.5em]{}{0ex}}\frac{3}{2}\omega (G)\rfloor -1\}$. Moreover, the bound is tight. Indeed, for any k∈N $k\in {\mathbb{N}}$ and k≥3 $k\ge 3$, there is a (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graph G $G$ with ω(G)=k $\omega (G)=k$ and χ(G)=max{k+3,⌊32k⌋−1} $\chi (G)=\max \{k+3,\lfloor \phantom{\rule[-0.5em]{}{0ex}}\frac{3}{2}k\rfloor -1\}$. [ABSTRACT FROM AUTHOR]

Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function f : N → N ∪ { ∞ } with f (1) = 1 and f (n) ⩾ 3 n + 1 3 , we construct a hereditary class of graphs G such that the maximum chromatic number of a graph in G with clique number n is equal to f(n) for every n ∈ N . In particular, we prove that there exist hereditary classes of graphs that are χ -bounded but not polynomially χ -bounded. [ABSTRACT FROM AUTHOR]

For a simple graph G with n vertices and m edges, let D (G) = diag (d 1 , d 2 , ⋯ , d n) be its diagonal matrix, where d i = deg (v i) , for all i = 1 , 2 , ⋯ , n and A(G) be its adjacency matrix. The matrix Q (G) = D (G) + A (G) is called the signless Laplacian matrix of G. If q 1 , q 2 , ⋯ , q n are the signless Laplacian eigenvalues of Q(G) arranged in a non-increasing order, let S k + (G) = ∑ i = 1 k q i be the sum of the k largest signless Laplacian eigenvalues of G. As the signless Laplacian matrix Q(G) is a positive semi-definite real symmetric matrix, so the spectral invariant S k + (G) actually represents the Ky Fan k-norm of the matrix Q(G). Ashraf et al. (Linear Algebra Appl 438:4539–4546, 2013) conjectured that , for all k = 1 , 2 , ⋯ , n . In this paper, we obtain upper bounds to S k + (G) for some infinite families of graphs. Those structural results and tools are applied to show that the conjecture holds for many classes of graphs, and in particular for graphs with a given clique number. [ABSTRACT FROM AUTHOR]

Let R be a finite ring (with nonzero identity) and let B i (G R) denote the unitary one-matching bi-Cayley graph over R. In this paper, we calculate the chromatic, edge chromatic, clique and independent numbers of B i (G R) and we show that the graph B i (G R) is a strongly regular graph if and only if | R | = 2. Also, we study the perfectness of B i (G R). Moreover, we prove that if B i (G R) ≅ B i (G S) and ω (G R) ≠ 2 , then G R ≅ G S and B i (G R / J R ) ≅ B i (G S / J S ) , where J R and J S are Jacobson radicals of R and S , respectively. Furthermore, for a finite field with ≠ ℤ 2 and a ring S , we prove that if B i (G M n ()) ≅ B i (G S) , where n > 1 is an integer, then S ≅ M n () , and so S is a semisimple ring. [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]

The Sombor index is defined as S O (G) = ∑ u v ∈ E (G) d 2 (u) + d 2 (v) , where d (u) and d (v) represent the number of edges in the graph G connected to the vertices u and v, respectively. In this paper, we characterize the largest and second largest Sombor indexes with a given number of cut edges. Moreover, we determine the upper and lower sharp bounds of the Sombor index with a given number of clique numbers, and we characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

A graph G of order n is called k-step Hamiltonian for k ≥ 1 if we can label the vertices of G as v1, v2,..., vn such that d(vn, v1) = d(vi, vi+1) = k for i = 1, 2,..., n-1. The (vertex) chromatic number of a graph G is the minimum number of colors needed to color the vertices of G so that no pair of adjacent vertices receive the same color. The clique number of G is the maximum cardinality of a set of pairwise adjacent vertices in G. In this paper, we study the chromatic number and the clique number in k-step Hamiltonian graphs for k ≥ 2. We present upper bounds for the chromatic number in k-step Hamiltonian graphs and give characterizations of graphs achieving the equality of the bounds. We also present an upper bound for the clique number in k-step Hamiltonian graphs and characterize graphs achieving equality of the bound. [ABSTRACT FROM AUTHOR]

Cartesian product, tensor product, and strong product are well-known product graphs, which have been studied in detail. Some of these products are generalized by defining 2-Cartesian product, 2-tensor product, and distance product. Additionally, certain basic graph parameters of these products have been studied. Recently, a new graph product, 2-strong product graph has been defined, and the connectedness of this graph has been discussed. In this paper, we studied chromatic number and clique number of 2-strong product graph. [ABSTRACT FROM AUTHOR]

Let G be a finite abelian group. The square power graph of G is a special type of an undirected simple finite graph whose vertex set is group G itself and two distinct vertices a, b ∈ G are adjacent if and only if a + b = 2c for some c ∈ G and 2c ≠ e (e is identity of group G). In this paper, we have studied the structure and various structural properties of square power graph such as degree of a vertex, diameter, girth, connectedness, independent number, clique number, etc for finite abelian group. We have introduced and studied extended square power graph. We have also discussed about prime labeling of square power graph and extended square power graph. [ABSTRACT FROM AUTHOR]

Let \( R \) be a finite commutative ring with unity. We have introduced a divisor graph of the ring, denoted by \( D[R] \). It is an undirected simple graph with a vertex set \( V = R - \{0, 1\} \), and two distinct vertices \( u \) and \( v \) in \( V \) are adjacent if and only if there exists \( w \in R \) such that \( v = uw \) or \( u = vw \). Clearly, \( 0 \) and unit elements are adjacent to all elements of the ring. Thus, we adopt the idea of Anderson and Livingston and remove the zero and unit vertices from the vertex set. A new graph is called the modified divisor graph, noted by symbol \( D_0[R] \).In this study, we have focused on the structural properties of \( D_0[\mathbb{Z}_n] \). Moreover, we have determined the diameter, girth, clique number, vertex connectivity, and edge connectivity of \( D_0[\mathbb{Z}_n] \) for every natural number \( n \). The purpose of studying this graph is to find relationships between the ring theoretic properties of \( R \) and the graph theoretic properties of \( D_0[R] \).

For a nontrivial finite group G, the intersection graph Γ (G) of G is the simple undirected graph whose vertices are the nontrivial proper subgroups of G and two vertices are joined by an edge if and only if they have a nontrivial intersection. In a finite simple graph Γ , the clique number of Γ is denoted by ω (Γ) . In this paper we show that if G is a finite group with ω (Γ (G)) < 13 , then G is solvable. As an application, we characterize all non-solvable groups G with ω (Γ (G)) = 13 . Moreover, we determine all finite groups G with ω (Γ (G)) ∈ { 2 , 3 , 4 } . [ABSTRACT FROM AUTHOR]

Let G and H be two vertex disjoint graphs. The union G ∪ H is the graph with V (G ∪ H) = V (G) ∪ (H) and E (G ∪ H) = E (G) ∪ E (H) . The join G + H is the graph with V (G + H) = V (G) ∪ V (H) and E (G + H) = E (G) ∪ E (H) ∪ { x y | x ∈ V (G) , y ∈ V (H) } . We use P k to denote a path on k vertices, use fork to denote the graph obtained from K 1 , 3 by subdividing an edge once, and use crown to denote the graph K 1 + K 1 , 3 . In this paper, we show that (i) χ (G) ≤ 3 2 (ω 2 (G) - ω (G)) if G is (crown, P 5 )-free, (ii) χ (G) ≤ 1 2 (ω 2 (G) + ω (G)) if G is (crown, fork)-free, and (iii) χ (G) ≤ 1 2 ω 2 (G) + 3 2 ω (G) + 1 if G is (crown, P 3 ∪ P 2 )-free. [ABSTRACT FROM AUTHOR]

Let G be a graph. We denote the chromatic (clique) number of G by χ (G) (ω (G)) . In this paper, we prove that (i) χ (G) ≤ 2 ω (G) if G is ( P 3 ∪ P 2 , kite)-free, (ii) χ (G) ≤ ω 2 (G) if G is ( P 3 ∪ P 2 , hammer)-free, (iii) χ (G) ≤ 3 ω 2 (G) + ω (G) 2 if G is ( P 3 ∪ P 2 , C 5 )-free. Furthermore, we also discuss the chromatic number of ( P 3 ∪ P 2 , K 4 )-Free Graphs. [ABSTRACT FROM AUTHOR]

Graph theory can give a representation of abstract mathematical systems such as groups or rings. We have many graph representations for a group, in this study we use the coprime graph representation for a generalized quaternion group to find the numerical invariants of the graph, which are the clique number and the chromatic number. The main results obtained from this study are the clique number of the coprime graph representation for the generalized quaternion group is equal to the chromatic number of the coprime graph representation for the generalized quaternion group for each case of the order.

Let Gn$$ {G}_n $$ be a random geometric graph, and then for q,p∈[0,1)$$ q,p\in \left[0,1\right) $$ we construct a (q,p)$$ \left(q,p\right) $$‐perturbed noisy random geometric graphGnq,p$$ {G}_n^{q,p} $$ where each existing edge in Gn$$ {G}_n $$ is removed with probability q$$ q $$, while and each non‐existent edge in Gn$$ {G}_n $$ is inserted with probability p$$ p $$. We give asymptotically tight bounds on the clique number ωGnq,p$$ \omega \left({G}_n^{q,p}\right) $$ for several regimes of parameter. [ABSTRACT FROM AUTHOR]

The rings considered in this article are commutative with identity which are not integral domains. Let R be a ring. An ideal I of R is said to be an annihilating ideal of R if there exists r ∊ R\{0} such that Ir = (0). Let A(R) denote the set of all annihilating ideals of R and let A(R)* = A(R)\{(0)}. Recall that the annihilating-ideal graph of R, denoted by AG(R), is an undirected graph whose vertex set is A(R)* and distinct vertices I and J are adjacent in this graph if and only if IJ = (0). The aim of this article is to characterize zero-dimensional rings such that the clique number of their annihilating-ideal graphs is at most four. [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]

In this paper, we introduce a way of illustrating a vector space in the vector graph in a way up to isomorphism there is a precise correspondence between such a graph and the vector space. Then, we find some relation between the graph properties and the space dimension. We also explore the clique and chromatic number and connectivity. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with unity 1≠0. In this paper, we completely describe the vertex and the edge chromatic number of the compressed zero divisor graph of the ring of integers modulo n. We find the clique number of the compressed zero divisor graph ΓE(Zn) of Zn and show that ΓE(Zn) is weakly perfect. We also show that the edge chromatic number of ΓE(Zn) is equal to the largest degree proving that ΓE(Zn) resides in class 1 family of graphs. [ABSTRACT FROM AUTHOR]