Search

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]

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]

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

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]

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]

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]

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]

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]

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]

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]

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]

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 non-trivial group. The intersection graph $\Gamma(G)$, is a graph whose vertices are all proper non-trivial subgroups of $G$, and there is an edge between two distinct vertices $H $ and $K$ if and only if $H\cap K\neq 1$. In this paper, we determine the clique number of the intersection graph of the cyclic groups of orders having at most three primes in their decomposition.1. IntroductionLet $G$ be a finite group. There are several ways to associate a graph to $G$ (see [7] and the references therein). The one we will consider in this paper, is denoted by $\Gamma(G)$ and is called the intersection graph of $G$. The intersection graph $\Gamma(G)$ of a nontrivial group $G$ is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of $G$, and there is an edge between two distinct vertices $H $ and $K$ if and only if $H\cap K\neq 1$ where 1 denotes the trivial subgroup of $G$. The graph $\Gamma(G)$ has been extensively studied ( see, for example, [1, 8, 11, 12]). Currently, the present authors in [4], have determined all groups $G$ such that the clique number of $\Gamma(G)$ is less than 5, and also they have given a criterion for solvability of finite groups $G$, by the clique number of $\Gamma(G)$. More precisely, it has been proved that if $G$ is a finite group such that the clique number of $\Gamma(G)$ is less than 13, then $G$ is solvable. Note that 13 is the clique number of $\Gamma(A_5)$, where $A_5$ is the alternating group on 5 letters. Other researches in this topic are intersection graphs of a semigroup, a module, and ideals of a ring, were investigated in [5], [2] and [6, 10], respectively. 2. Main ResultsWe start this section with the following definition:Definition 2.1. The subset $X$ of vertices of a finite graph $\Gamma$ is called a {\it clique}, if the induced subgraph by $X$ is a complete graph. The maximum size of a clique, among all cliques of $\Gamma$, is called the clique number of $\Gamma$ and we denote it by $\omega(\Gamma)$. If $\Gamma$ is empty (without vertex), then we define $\omega(\Gamma)=0$ and $\omega(\Gamma)=1$ if $\Gamma$ is null (with a non-empty vertex set with no edges). A clique $X$ in $\Gamma$ is called {\it maximal} if there is no clique $Y$ in $\Gamma$ such that $X\subsetneq Y$. Note that the maximum size, among all maximal cliques in $\Gamma(G)$, is $\omega(\Gamma(G))$. To prove the main theorems, we need the following result that its proof can be found in the most valid book of group theory. Proposition 2.2. If $G=\langle g\rangle$ is a cyclic group of ordsr $n$, then for any divisor $s$ of $n$, there is a unique subgroup $H=\langle g^{\frac{n}{s}}\rangle$ of $G$ of order $s$. The following result is a consequence of the above proposition. Corollary 2.3. Let $G$ be a finite cyclic group. Then, the intersection of two proper subgroups of $G$ is non-trivial if and only if their orders are not relatively prime. For a natural number $n$, we denote by $C_n$ the cyclic group of order $n$, $\pi(n)$ the set of prime divisors of $n$ and $d(n)$ the number of all divisors of $n$. Note that if $p$ is a prime number and $n$ is a multiple of $p$, then the number of divisors of $n$ with multiple $p$ is $d(\frac{n}{p})$. If $V(\Gamma(G))$ is the set of vertices of $\Gamma(G)$, then by Proposition 2.2, we have $|V(\Gamma(C_n))|=d(n)-2$. In this paper, we obtain $\omega(\Gamma(C_n))$, where $|\pi(n)|=3$. 3. Summary of Proofs/ConclusionsNow, we state and prove our main results. First, we find the clique number of a cyclic group of a prime power order. Proposition 3.1. If $p$ is a prime and $m$ is a positive integer, then $\omega(\Gamma(C_{p^m}))=m-1$.Proof. Since $|V(\Gamma(C_n))|=d(n)-2$ and $d(p^m)=m+1$, we get the conclusion. In the sequel, assume that $p_1, p_2$ and $p_3$ are distinct primes. Also assume that $n_1, n_2$ and $n_3$ are positive integers such that $n_1\geq n_2\geq n_3$. In the following results, we obtain the clique number of the intersection graph of group $C_{p_1^{n_1}p_2^{n_2}}$. We recall that $d(p_1^{n_1}p_2^{n_2})=(n_1+1)(n_2+1)$. Proposition 3.2. We have$\omega(\Gamma(C_{p_1^{n_1}p_2^{n_2}}))=d(p_1^{n_1}p_2^{n_2})-2-d(p_2^{n_2})=n_1n_2+n_1-1$. Proof. Suppose that $G=C_{p_1^{n_1}p_2^{n_2}}$. Then, we define the subsets of $V(\Gamma(G))$ as follows: ♦ For $1\leq i\leq 2$, $V_{p_i}(\Gamma(G))$ is the set of all proper subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i\}$. ♦ $V_{p_1p_2}(\Gamma(G))$ is the set of all proper subgroups $H$ of $G$ such that $\pi(|H|)=\{p_1, p_2\}$. It is clear that $\{V_{p_1}(\Gamma(G)), V_{p_2}(\Gamma(G)), V_{p_1p_2}(\Gamma(G)) \}$ forms a partition for $V(\Gamma(G))$. By Proposition 2.2, we have $|V_{p_i} (\Gamma(G))|=d(p_i^{n_i})-1=n_i$ and $|V_{p_1p_2}(\Gamma(G))|=d(\frac{n}{p_1p_2})-1=n_1n_2-1$. By Corollary 2.3, in $\Gamma(G)$, each element of the clique $V_{p_1}(\Gamma(G))$ does not join to any element of the clique $V_{p_2}(G)$ and moreover all elements of $V_{p_i}(\Gamma(G))$ for $i=1, 2$ join to all elements of the clique $V_{p_1p_2}(G)$. Therefore $V_{p_1}(\Gamma(G))\cup V_{p_1p_2}(\Gamma(G))$ and $V_{p_2}(\Gamma(G))\cup V_{p_1p_2}(\Gamma(G))$ are the only maximal cliques of $\Gamma(G)$ and since $n_1\geq n_2$, we have the result.Now we state the last main result. Theorem 3.3. Let $G= C_n$ where $n=p_1^{n_1}p_2^{n_2}p_3^{n_3}$. Then\\(1) If $n_1\geq n_2n_3$, then $\omega(\Gamma(G))=d(\frac{n}{p_1})-1=n_1+n_1n_2+n_1n_3+n_1n_2n_3-1$.\\(2) If $n_1\leq n_2n_3$, then $\omega(\Gamma(G))=d(\frac{p_1^{n_1}p_2^{n_2}}{p_1p_2})+d(\frac{p_1^{n_1}p_3^{n_3}}{p_1p_3})+d(\frac{p_2^{n_2}p_3^{n_3}}{p_2p_3})+d(\frac{n}{p_1p_2p_3})-1$\\$$\hspace{5cm}=n_1n_2+n_1n_3+n_2n_3+n_1n_2n_3-1.~~~~~~~~~~~~~~~~~~~~~~~\hspace{4cm}$$Proof. Similar to the proof of Proposition 3.2, we define the subsets of $V(\Gamma(G))$ as follows:\\♦ For $1\leq i\leq 3$, $V_{p_i}(\Gamma(G))$ is the set of all subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i\}$. Therefore, $|V_{p_i}(\Gamma(G))|=d(p_i^{n_i})-1=n_i$.♦ $V_{p_ip_j}(\Gamma(G))$ is the set of all subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i, p_j\}$ for $1\leq i

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]

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] \).

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.

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

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]

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]

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]

In this paper, we study the class of graphs Gm,n that have the same degree sequence as two disjoint cliques Km and Kn, 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 Gm,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.

The Sombor index is defined as SO(G)=∑uv∈E(G)d2(u)+d2(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.

Let F t (n) denote the family of all connected graphs of order n with clique number t. In this paper, we present a new upper bound for the chromatic polynomial of a graph G in F t (n) in terms of the clique number of G. Moreover, we also show that the conjecture proposed by Tomescu, which says that if x ≥ k ≥ 4 and G is a connected graph on n vertices with chromatic number k, then P (G , x) ≤ (x) k (x - 1) n - k holds under certain conditions, where (x) k = x (x - 1) ⋯ (x - k + 1) , such as the clique number ω (G) = k ≥ 4 , ω (G) = k - 1 (k ≥ 7) with two (k - 1) -cliques having at most k - 3 vertices in common, or maximum degree ▵ (G) = n - 2 . [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with non-zero identity. Khojasteh and Nikmehr (Can. Math. 60(2), 319–328, 2017) introduced the weakly nilpotent graph Γ w (R) of a commutative ring R, whose vertices are R ∗ = R \ { 0 } and two distinct vertices x and y are adjacent if and only if x y ∈ N (R) ∗ , where N (R) ∗ is the set of all non-zero nilpotent elements of R. In this paper, we extend some more results such as the connectedness, the completeness, the bipartiteness and the domination number of Γ w (R) . We also study some properties on the complement of the weakly nilpotent graph Γ w (R) ¯ of a commutative ring. [ABSTRACT FROM AUTHOR]

In this paper, we mainly investigate graphs with a small (strong) proper connection number and a large clique number. First, we discuss the (strong) proper connection number of a graph G of order n and ω (G) = n − i for 1 ⩽ i ⩽ 3 . Next, we investigate the rainbow connection number of a graph G of order n, d i a m (G) ≥ 3 and ω (G) = n − i for 2 ⩽ i ⩽ 3 . [ABSTRACT FROM AUTHOR]

Let S (m , e) be a class of numerical semigroups with multiplicity m and embedding dimension e. We call a graph G S an S (m , e) -graph if there exists a numerical semigroup S ∈ S (m , e) with V (G S) = { x : x ∈ g (S) } and E (G S) = { x y ⇔ x + y ∈ S } , where g (S) denotes the gap set of S. The aim of this article is to discuss the planarity of S (m , e) -graphs for some cases where S is an irreducible numerical semigroup. [ABSTRACT FROM AUTHOR]