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]

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

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.

In this work, we are interested in the subgraph of unitary Cayley graph of a matrix algebra over a finite field induced by the set of idempotent matrices. We study its structure and completely obtain all connected components with the degree on each vertex. Most of them turn out to be a regular bipartite graph such that each partite set has the same number of vertices. Our main tools are combinatorial results on matrix algebras. Moreover, we compute the clique number, chromatic number and independence number of the graph. [ABSTRACT FROM AUTHOR]

We use P 5 to denote a path of length 5 and C 5 to denote a cycle of length 5. The aim of this paper is to prove that, if G is a connected graph satisfying (1). G has an induced C 5 and no clique cut-set, (2). G has no induced subgraph isomorphic to P 5 or K 5 − e , then G is max ⁡ { 13 , ω (G) + 1 } -colorable. • If a non-bipartite (P 5 , diamond)-free graph is not a complete graph or a 5-ring, then it contains an induced paw. • Let G be a (P 5 , K 5 − e)-free graph with an induced 5-cycle C. If G has an induced T -5-wheel Σ, then χ (G) ≤ max ⁡ { 13 , ω (G) + 1 }. • Let G be (P 5 , K 5 − e)-free with an induced C 5. Then χ (G) ≤ max ⁡ { 13 , ω (G) + 1 }. [ABSTRACT FROM AUTHOR]