Search

We revisit the maximal clique enumeration algorithm cliques by Tomita et al. that appeared in Theoretical Computer Science in 2006. It is known to work in O ( 3 n / 3 ) -time in the worst-case for an n-vertex graph. This is worst-case optimal with respect to the input size, but there is little knowledge about its performance with respect to the output. In this paper, we extend the time-complexity analysis with respect to the maximum size and the number of maximal cliques, and to its delay, solving issues that were left as open problems since the original paper. In particular, we prove that cliques has Ω ( 3 n / 6 ) delay and that, even if we allow to change the pivoting strategy, a variant having polynomial delay cannot be designed unless P = N P . These same results apply to the related Bron-Kerbosch algorithm. On the positive side, we show that the complexity of cliques and Bron-Kerbosch is amortized polynomial on graphs with logarithmic clique number. As these algorithms are widely used and regarded as fast “in practice”, we are interested in observing their practical behavior: we run an evaluation of cliques and three Bron-Kerbosch variants on over 130 real-world and synthetic graphs, observing how the clique number almost always satisfies our logarithmic constraint, and that their performance seems far from its theoretical worst-case behavior in terms of both total time and delay. 1

In this paper, we introduce a graph topological structure called Inclusion Graph of a Topology . The diameter, girth, connectivity, maximal independent sets, different variants of domination number...

For 0 ≤ α ≤ 1 , the A α -matrix of graph G is defined as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) , where D ( G ) and A ( G ) are the diagonal matrix of the degrees and the adjacency matrix of G, respectively. On the premise of a fixed number of edges, Zhai et al. (2020) [15] depicted the extremal graph which has the largest A 1 2 -spectral radius, and also characterized the graph maximizing the A 1 2 -spectral radius among all graphs with given clique number (respectively, chromatic number). In this paper, we extend the conclusion of them to A α -spectral radius for α ∈ [ 1 2 , 1 ] .

Let [Formula: see text] be a commutative ring and [Formula: see text] be its zero-divisor graph. We completely determine the structure of all finite commutative rings whose zero-divisor graphs have clique number one, two, or three. Furthermore, if [Formula: see text] (each [Formula: see text] is local for [Formula: see text]), we also give algebraic characterizations of the ring [Formula: see text] when the clique number of [Formula: see text] is four.

Let $$h=\prod _{i=1}^{t}p_i^{s_i}$$ be its decomposition into a product of powers of distinct primes, and $$\mathbb {Z}_{h}$$ be the residue class ring modulo h. Let $$1\le r\le \min \{m,n\}$$ and $$\mathbb {Z}_{h}^{m\times n}$$ be the set of all $$m\times n$$ matrices over $$\mathbb {Z}_{h}$$ . The generalized bilinear forms graph over $$\mathbb {Z}_{h}$$ , denoted by $$\hbox {Bil}_r\left( \mathbb {Z}_{h}^{m\times n}\right) $$ , has the vertex set $$\mathbb {Z}_{h}^{m\times n}$$ , and two distinct vertices A and B are adjacent if the inner rank of $$A-B$$ is less than or equal to r. In this paper, we determine the clique number and geometric structures of maximum cliques of $$\hbox {Bil}_r\left( \mathbb {Z}_{h}^{m\times n}\right) $$ . As a result, the Erdős-Ko-Rado theorem for $$\mathbb {Z}_h^{m\times n}$$ is obtained.

Let R be a commutative Artinian ring and let ΓE(R) be the compressed zero-divisor graph associated to R. The question of when the clique number ω(ΓE(R))

In this paper, we introduce a graph topological structure, called Intersection Graph Iτ(X) = (V(τ), E(τ)), where V(τ) = Collection of all topologies defined on X other than τi and τd and for τ1, τ2...

Let H be a 3-uniform hypergraph of order n with clique number $$\omega (H)=k$$ ω ( H ) = k . Assume that the union of the k-cliques of H equals its vertex set, the intersection of all maximum cliques of H is empty, but the intersection of all but one k-clique is non-empty. For fixed $$m=n-k$$ m = n - k , Szemerédi and Petruska conjectured the sharp bound $$n\hbox {\,\,\char 054\,\,}{m+2\atopwithdelims ()2}$$ n 6 m + 2 2 . In this note the conjecture is verified for $$m=2,3$$ m = 2 , 3 and 4.

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, diam(G)≥3 and ω(G)=n−i for 2⩽i⩽3.

In 2013, C. Godsil introduced the quantum version of Hedetniemi’s conjecture. To solve this conjecture, we introduce the concept of quantum multiplicative graph and obtain a necessary and sufficien...

The spectral radius (or the signless Laplacian spectral radius) of a general hypergraph is the maximum modulus of the eigenvalues of its adjacency (or its signless Laplacian) tensor. In this paper, we firstly obtain a lower bound of the spectral radius (or the signless Laplacian spectral radius) of general hypergraphs in terms of clique number. Moreover, we present a relation between a homogeneous polynomial and the clique number of general hypergraphs. As an application, we finally obtain an upper bound of the spectral radius of general hypergraphs in terms of clique number.

Let c ( G ) , g ( G ) , ω ( G ) and μ n − 1 ( G ) denote the number of components, the girth, the clique number and the second smallest Laplacian eigenvalue of the graph G, respectively. The strength η ( G ) and the fractional arboricity γ ( G ) are defined by η ( G ) = min F ⊆ E ( G ) ⁡ | F | c ( G − F ) − c ( G ) and γ ( G ) = max H ⊆ G ⁡ | E ( H ) | | V ( H ) | − 1 , where the optima are taken over all edge subsets F and all subgraphs H whenever the denominator is non-zero, respectively. Nash-Williams and Tutte proved that G has k edge-disjoint spanning trees if and only if η ( G ) ≥ k ; and Nash-Williams showed that G can be covered by at most k forests if and only if γ ( G ) ≤ k . In this paper, for integers r ≥ 2 , s and t, and any simple graph G of order n with minimum degree δ ≥ 2 s t and either clique number ω ( G ) ≤ r or girth g ≥ 3 , we prove that if μ n − 1 ( G ) > 2 s − 1 t φ ( δ , r ) or μ n − 1 ( G ) > 2 s − 1 t N ( δ , g ) , then η ( G ) ≥ s t , where φ ( δ , r ) = max ⁡ { δ + 1 , ⌊ r δ r − 1 ⌋ } and N ( δ , g ) is the Moore bound on the smallest possible number of vertices such that there exists a δ-regular simple graph with girth g. As corollaries, sufficient conditions on μ n − 1 ( G ) such that G has k edge-disjoint spanning trees are obtained. Analogous result involving μ n − 1 ( G ) to characterize fractional arboricity of graphs with given clique number is also presented. Former results in Liu et al. (2014) [17] and Hong et al. (2016) [11] are extended, and the result in Liu et al. (2019) [18] is improved.

The Babai numbers and the upper chromatic number are parameters that can be assigned to any metric space. They can, therefore, be assigned to any connected simple graph. In this paper we make progress in the theory of the first Babai number and the upper chromatic number in the simple graph setting, with emphasis on graphs of diameter 2.

Let $\kappa'(G)$, $\kappa(G)$, $\mu_{n-1}(G)$ and $\mu_1(G)$ denote the edge-connectivity, vertex-connectivity, the algebraic connectivity and the Laplacian spectral radius of $G$, respectively. In this paper, we prove that for integers $k\geq 2$ and $r\geq 2$, and any simple graph $G$ of order $n$ with minimum degree $\delta\geq k$, girth $g\geq 3$ and clique number $\omega(G)\leq r$, the edge-connectivity $\kappa'(G)\geq k$ if $\mu_{n-1}(G) \geq \frac{(k-1)n}{N(\delta,g)(n-N(\delta,g))}$ or if $\mu_{n-1}(G) \geq \frac{(k-1)n}{\varphi(\delta,r)(n-\varphi(\delta,r))}$, where $N(\delta,g)$ is the Moore bound on the smallest possible number of vertices such that there exists a $\delta$-regular simple graph with girth $g$, and $\varphi(\delta,r) = \max\{\delta+1,\lfloor\frac{r\delta}{r-1}\rfloor\}$. Analogue results involving $\mu_{n-1}(G)$ and $\frac{\mu_1(G)}{\mu_{n-1}(G)}$ to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in [Linear Algebra Appl. 439 (2013) 3777--3784], [Linear Algebra Appl. 578 (2019) 411--424], [Linear Algebra Appl. 579 (2019) 72--88], [Appl. Math. Comput. 344-345 (2019) 141--149] and [Electronic J. Linear Algebra 34 (2018) 428--443] are improved or extended., Comment: 14 pages

In this paper we show that it can be decided in polynomial time whether or not the visibility graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be constructed in polynomial time. We show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4.

The signless Laplacian spectral radius of a graph is the largest eigenvalue of its signless Laplacian matrix. In the paper, the graph with maximal signless Laplacian spectral radius among all graphs with given size and clique number is characterized. As applications, we determine the graph with maximal signless Laplacian spectral radius among all graphs with given size, and characterize the graph with maximal signless Laplacian spectral radius among all graphs with given size and chromatic number.

In this paper, we introduce the zero-divisor graph of a poset with respect to an automorphism, called the generalized zero-divisor graph of a poset, as an extension of the zero-divisor graph of a poset. It is proved that for such graphs, the chromatic number and the clique number need not be equal. A sufficient condition is provided for the chromatic number and the clique number of the generalized zero-divisor graph to be equal, which extends the result of the zero-divisor graph of poset. Further, the connectedness, diameter and girth of such graphs are studied.

A γ-quasi-clique in a simple undirected graph refers to a subset of vertices that induces a subgraph with edge density at least γ. When γ equals one, this definition corresponds to a classical clique. When γ is less than one, it relaxes the requirement of all possible edges by the clique definition. Quasi-clique detection has been used in graph-based data mining to find dense clusters, especially in large-scale error-prone data sets in which the clique model can be overly restrictive. The maximum γ-quasi-clique problem, seeking a γ-quasi-clique of maximum cardinality in the given graph, can be formulated as an optimization problem with a linear objective function and a single quadratic constraint in binary variables. This article investigates the Lagrangian dual of this formulation and develops an upper-bounding technique using the geometry of ellipsoids to bound the Lagrangian dual. The tightness of the upper bound is compared with those obtained from multiple mixed-integer programming formulations of the problem via experiments on benchmark instances.

This paper explores the connections between the classical maximum clique problem and its edge-weighted generalization, the maximum edge weight clique (MEWC) problem. As a result, a new analytic upper bound on the clique number of a graph is obtained and an exact algorithm for solving the MEWC problem is developed. The bound on the clique number is derived using a Lagrangian relaxation of an integer (linear) programming formulation of the MEWC problem. Furthermore, coloring-based bounds on the clique number are used in a novel upper-bounding scheme for the MEWC problem. This scheme is employed within a combinatorial branch-and-bound framework, yielding an exact algorithm for the MEWC problem. Results of computational experiments demonstrate a superior performance of the proposed algorithm compared with existing approaches.

A signed relative clique number of signed graph (where edges are assigned positive or negative signs) is the size of a largest subset X of vertices such that every two vertices are either adjacent or are part of a 4-cycle with an odd number of negative edges. The signed relative clique number is sandwiched between two other parameters of signed graphs, namely, the signed absolute clique number and the signed chromatic number, all three notions defined in Naserasr et al. (2014). Thus, together with a result from Ochem et al. (2016) the lower bound of 8 and upper bound of 40 has already been proved for the signed relative clique number of the family of planar graphs. Here we improve the upper bound to 15. Furthermore, we determine the exact values of signed relative clique number of the families of outerplanar graphs and triangle-free planar graphs.

In this paper, we define a homogeneous polynomial for a general hypergraph, and establish a remarkable connection between clique number and the homogeneous polynomial of a general hypergraph. For a general hypergraph, we explore some inequality relations among spectral radius, clique number and the homogeneous polynomial. We also give lower and upper bounds on the spectral radius of a general hypergraph in terms of the clique number.

The notions of critical ideals and characteristic ideals of graphs are introduced by Corrales and Valencia to study properties of graphs, including clique number, zero forcing number, minimum rank and critical group. In this paper, we provide methods to compute critical ideals of complete multipartite graphs and obtain complete answers for the characteristic ideals of complete multipartite graphs.

A set of lines through the origin in Euclidean space is called equiangular when any pair of lines from the set intersects with each other at a common angle. We study the maximum size of equiangular lines in Euclidean space and use graph theoretic approach to prove that all the currently known construction for maximum equiangular lines in $\mathbb R^d$ cannot add another line to form a larger equiangular set of lines if $14 \leq d \leq 20$ and $d \neq 15$. We give new constructions of large equiangular lines which are 248 equiangular lines in $\mathbb R^{42}$, 200 equiangular lines in $\mathbb{R}^{41}$, 168 equiangular lines in $\mathbb{R}^{40}$, 152 equiangular lines in $\mathbb R^{39}$ with angle $1/7$, and 56 equiangular lines in $\mathbb R^{18}$ with angle $1/5$., 6 pages; title changed; new results about constructions of large equiangular sets are added in Section 3

Let G be a simple graph with order n and size m and having Laplacian eigenvalues μ 1 , μ 2 , … , μ n − 1 , μ n = 0 and let S k ( G ) = ∑ i = 1 k μ i be the sum of k largest Laplacian eigenvalues of G. Brouwer conjectured that S k ( G ) ≤ m + ( k + 1 2 ) , for all k = 1 , 2 , … , n . We obtain upper bounds for S k ( G ) , in terms of the clique number ω, the order n and integers p ≥ 0 , r ≥ 1 , s 1 ≥ s 2 ≥ 2 associated to the structure of the graph G. We discuss Brouwer's conjecture for two large families of graphs; the first family of graphs is obtained from a clique of size ω by identifying each of its vertices to a vertex of an arbitrary c-cyclic graph, and the second family is composed of the graphs in which the removal of the edges of the maximal complete bipartite subgraph gives a graph each of whose non-trivial components is a c-cyclic graph. We show among these two large families of graphs, the Brouwer's conjecture holds for various subfamilies of graphs depending upon the value of c, the order of the c-cyclic graphs, the clique number of the graph, the order of the maximal complete bipartite subgraph and the number of the c-cyclic components of the graph.

Let R be an unital ring which is not necessarily commutative. The intersection graph of ideals of R is a graph with the vertex set which contains proper ideals of R and distinct two vertices I and ...

It is shown that a finite-dimensional formally real simple Jordan algebra is completely determined by the relation of Jordan-orthogonality.Communicated by Prof. Alberto Elduque

Let G be a finite group, and let cd ( G ) denote the set of degrees of the irreducible complex characters of G . The degree graph Δ ( G ) of G is defined as the simple undirected graph whose vertex set V ( G ) consists of the prime divisors of the numbers in cd ( G ) , two distinct vertices p and q being adjacent if and only if pq divides some number in cd ( G ) . In this note, we provide an upper bound on the size of V ( G ) in terms of the clique number ω ( G ) (i.e., the maximum size of a subset of V ( G ) inducing a complete subgraph) of Δ ( G ) . Namely, we show that | V ( G ) | ≤ max { 2 ω ( G ) + 1 , 3 ω ( G ) − 4 } . Examples are given in order to show that the bound is best possible. This completes the analysis carried out in [1] where the solvable case was treated, extends the results in [3] , [4] , [9] , and answers a question posed by the first author and H.P. Tong-Viet in [4] .

For a commutative ring R with non-zero zero-divisor set $$Z^*(R)$$, the zero-divisor graph of R is $$\varGamma (R)$$ with vertex set $$Z^*(R)$$, where two distinct vertices x and y are adjacent if and only if $$xy=0$$. The zero-divisor graph structure of $${\mathbb {Z}}_{p^n}$$ is described. We determine the clique number, degree of the vertices, size, metric dimension, upper dimension, automorphism group, Wiener index of the associated zero-divisor graph of $${\mathbb {Z}}_{p^n}$$. Further, we provide a partition of the vertex set of $$\varGamma ({\mathbb {Z}}_{p^n})$$ into distance similar equivalence classes and we show that in this graph the upper dimension equals the metric dimension. Also, we discuss similar properties of the compressed zero-divisor graph.

We prove a conjecture of Andras Gyarfas, that for all κ , l , every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least l.

Let $G = (V, E)$ be a connected graph of order $n$. $S \subseteq V$ is an edge metric generator of $G$ if any pair of edges in $E$ can be distinguished by some element of $S$. The edge metric dimension $edim(G)$ of a graph $G$ is the least size of an edge metric generator of $G$. In this paper, we give the characterization of all connected bipartite graphs with $edim = n-2$, which partially answers an open problem of Zubrilina (2018). Furthermore, we also give a sufficient and necessary condition for $edim(G) = n-2$, where $G$ is a graph with maximum degree $n-1$. In addition, the relationship between the edge metric dimension and the clique number of a graph $G$ is investigated by construction.

Let S(m,e) be a class of numerical semigroups with multiplicity m and embedding dimension e. We call a graph GS an S(m,e)-graph if there exists a numerical semigroup S∈S(m,e) with V(GS)={x:x∈g(S)} and E(GS)={xy⇔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.

Given a graph G and an interdiction budget k ∈ N , the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim of reducing the clique number of the graph. The EICP optimal solutions, called optimal interdiction policies, determine the subset of most vital edges of a graph which are crucial for preserving its clique number. We propose a new set-covering-based Integer Linear Programming (ILP) formulation for the EICP with an exponential number of constraints, called the clique-covering inequalities. We design a new branch-and-cut algorithm which is enhanced by a tailored separation procedure and by an effective heuristic initialization phase. Thanks to the new exact algorithm, we manage to solve the EICP in several sets of instances from the literature. Extensive tests show that the new exact algorithm greatly outperforms the state-of-the-art approaches for the EICP.

In this paper, clique number and girth of the rough ideal-based rough edge Cayley graphs [Formula: see text] and [Formula: see text], where [Formula: see text] is the rough Ideal of the rough semiring [Formula: see text] and [Formula: see text] contains the nontrivial elements of [Formula: see text], are evaluated. We prove that the clique number of [Formula: see text] is [Formula: see text] and the clique number of [Formula: see text] is [Formula: see text]. Girth of [Formula: see text] and [Formula: see text] is 3. These concepts are illustrated with examples.

< p>The intersection graph $\\mathbb{Int}(A)$ of an $S$-act $A$ over a semigroup $S$ is an undirected simple graph whose vertices are non-trivial subacts of $A$, and two distinct vertices are adjacent if and only if they have a non-empty intersection. In this paper, we study some graph-theoretic properties of $\\mathbb{Int}(A)$ in connection to some algebraic properties of $A$. It is proved that the finiteness of each of the clique number, the chromatic number, and the degree of some or all vertices in $\\mathbb{Int}(A)$ is equivalent to the finiteness of the number of subacts of $A$. Finally, we determine the clique number of the graphs of certain classes of $S$-acts.

We study distance graphs with exponentially large chromatic number which do not contain cliques of prescribed size in the rational space.

Considering connected K 1 , 3 -free graphs with independence number at least 3, Chudnovsky and Seymour (2010) showed that every such graph, say G , is 2 ω -colourable where ω denotes the clique number of G . We study ( K 1 , 3 , Y ) -free graphs, and show that the following three statements are equivalent. • [(1)] Every connected ( K 1 , 3 , Y ) -free graph which is distinct from an odd cycle and which has independence number at least 3 is perfect. • [(2)] Every connected ( K 1 , 3 , Y ) -free graph which is distinct from an odd cycle and which has independence number at least 3 is ω -colourable. • [(3)] Y is isomorphic to an induced subgraph of P 5 or Z 2 (where Z 2 is also known as hammer). Furthermore, for connected ( K 1 , 3 , Y ) -free graphs (without an assumption on the independence number), we show a similar characterisation featuring the graphs P 4 and Z 1 (where Z 1 is also known as paw).

In this paper we introduced the definition of perfect foldingof graphs and we proved that cycle graphs of even number ofedges can be perfectly folded while that of odd number ofedges can be perfectly folded to C3 . Also we proved thatwheel graphs of odd number of vertices can be perfectlyfolded to C3. Finally we proved that if G is a graph of n verticessuch that 2 < clique number =chromatic number=k < n ,then the graph can be perfectly folded to a clique of order k.

A hole is an induced cycle of length at least 4, and a cap is obtained from a hole by adding a new vertex and joining it to exactly two adjacent vertices of the hole. Let G be a graph containing neither caps nor holes of even lengths as induced subgraphs. Cameron et al. (2018) showed that χ ( G ) ≤ ⌊ 3 ω ( G ) 2 ⌋ , and asked whether χ ( G ) ≤ ⌈ 5 ω ( G ) 4 ⌉ , where χ ( G ) and ω ( G ) denote the chromatic number and clique number of G , respectively. In this paper, we show that χ ( G ) ≤ ⌈ 4 ω ( G ) 3 ⌉ , and χ ( G ) ≤ ⌈ 5 ω ( G ) 4 ⌉ if G further has no 5-cycles sharing exactly one edge. This improves the conclusion of Cameron et al. (2018), and conditionally answers their question in affirmative.

Fix an oriented graph H , and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomorphic to H ? Kierstead and Rodl (1996) raised this question for two specific kinds of digraph H : the three-edge path, with the first and last edges both directed towards the interior; and stars (with many edges directed out and many directed in). Aboulker et al. (2018) subsequently conjectured that the answer is affirmative in both cases. We give affirmative answers to both questions.

Very recently, Aouchiche and Hansen gave an upper bound on the ratio of G A ∕ χ of the geometric–arithmetic index G A ( G ) and the chromatic number χ ( G ) of a graph. Furthermore, they proposed several conjectures on the relation between geometric–arithmetic index and chromatic number, and clique number. In this note, we disprove four of those conjectures. In addition, we present a sufficient condition for an edge e ∈ E ( G ) with G A ( G − e ) G A ( G ) .

Let R be a commutative ring and let M be an R-module. For a ∈ R, AnnM(a) = {m ∈ M : am = 0} is said to be an annihilator submodule of M. In this paper, we study the property of being prime or essential for annihilator submodules of M. Also, we introduce the annihilator essential graph of equivalence classes of zero divisors of M, AER(M), which is constructed from classes of zero divisors, determined by annihilator submodules of M and distinct vertices [a] and [b] are adjacent whenever AnnM(a) + AnnM(b) is an essential submodule of M. Among other things, we determine when AER(M) is a connected graph, a star graph, or a complete graph. We compare the clique number of AER(M) and the cardinal of m −AssR(M).

In the theory of dense graph limits, a graphon is a symmetric measurable function $W\colon[0,1]^2\to [0,1]$. Each graphon gives rise naturally to a random graph distribution, denoted $\mathbb{G}(n,...

We prove that every triangle-free graph with maximum degree $\Delta$ has list chromatic number at most $(1+o(1))\frac{\Delta}{\ln \Delta}$. This matches the best-known bound for graphs of girth at least 5. We also provide a new proof that for any $r\geq 4$ every $K_r$-free graph has list-chromatic number at most $200r\frac{\Delta\ln\ln\Delta}{\ln\Delta}$., Comment: Revised according to referee reports

A graph G with clique number $$\omega (G)$$ and chromatic number $$\chi (G)$$ is perfect if $$\chi (H)=\omega (H)$$ for every induced subgraph H of G. A family $${\mathcal {G}}$$ of graphs is called $$\chi $$ -bounded with binding function f if $$\chi (G') \le f(\omega (G'))$$ holds whenever $$G \in {\mathcal {G}}$$ and $$G'$$ is an induced subgraph of G. In this paper we will present a survey on polynomial $$\chi $$ -binding functions. Especially we will address perfect graphs, hereditary graphs satisfying the Vizing bound ( $$\chi \le \omega +1$$ ), graphs having linear $$\chi $$ -binding functions and graphs having non-linear polynomial $$\chi $$ -binding functions. Thereby we also survey polynomial $$\chi $$ -binding functions for several graph classes defined in terms of forbidden induced subgraphs, among them $$2K_2$$ -free graphs, $$P_k$$ -free graphs, claw-free graphs, and $${ diamond}$$ -free graphs. ( [])

The paper will present a method to establish an upper bound on the clique number of a given finite graph. In order to evaluate the proposed algorithm in practice we carry out a large scale numerical experiment.

For a simple graph G with order n and size m having Laplacian eigenvalues $$\mu _1, \mu _2, \dots , \mu _{n-1},\mu _n=0$$ , let $$S_k(G)=\sum _{i=1}^{k}\mu _i$$ , be the sum of k largest Laplacian eigenvalues of G. We obtain upper bounds for the sum of k largest Laplacian eigenvalues of two large families of graphs. As a consequence, we prove Brouwer’s Conjecture for large number of graphs which belong to these families of graphs.

The Mycielskian construction, denoted μ(G), takes a finite simple graph G to a larger graph with of the same clique number but larger chromatic number. The generalized Mycielskian construction, denoted μt(G), takes G to a larger graph with the same chromatic number but with larger odd girth. In this chapter we look at symmetry parameters of μ(G) and μt(G) in terms of the same parameters of G. These symmetry parameters include determining number, distinguishing number, and cost of distinguishing.

Funding: The research work of T. Tamizh Chelvam is supported by CSIR Emeritus Scientist Scheme (No. 21 (1123)/20/EMR-II) of Council of Scientific and Industrial Research, Government of India. Let G be a finite abelian group, written additively, and H a subgroup of G. The subgroup sum graph ΓG,H is the graph with vertex set G, in which two distinct vertices x and y are joined if x+y∈H∖{0}. These graphs form a fairly large class of Cayley sum graphs. Among cases which have been considered previously are the prime sum graphs, in the case where H=pG for some prime number p. In this paper we present their structure and a detailed analysis of their properties. We also consider the simpler graph Γ+G,H, which we refer to as the extended subgroup sum graph, in which x and y are joined if x+y∈H: the subgroup sum is obtained by removing from this graph the partial matching of edges having the form {x,−x} when 2x≠0. We study perfectness, clique number and independence number, connectedness, diameter, spectrum, and domination number of these graphs and their complements. We interpret our general results in detail in the prime sum graphs. Postprint