Cliques in rank-1 random graphs: The role of inhomogeneity Bogerd, Kay; Castro, Rui M.; van der Hofstad, Remco
Bernoulli : official journal of the Bernoulli Society for Mathematical Statistics and Probability,
02/2020, Volume:
26, Issue:
1
Journal Article
Let G be a graph, u and v two vertices of G and X a subset of V(G). A u−vgeodesic is a path between u and v of minimum length. Ig(u,v) is the set of vertices that lie on any u−v geodesic and Ig(X) is ...the set ⋃u,v∈XIg(u,v). X is g-convex if Ig(X)=X. The convexity number, con(G), of G is the maximum cardinality of a proper g-convex set of G. The clique number, ω(G), of G is the maximum cardinality of a clique of G. If G is a connected not complete graph then ω(G)≤con(G). In this paper a necessary condition for ω(G)=con(G) is provided and, on the basis of this condition, both the class of distance-hereditary graphs for which ω(G)=con(G) and the class of chordal graphs for which ω(G)=con(G) are characterized.
Let G be a simple graph with order n and size m and having Laplacian eigenvalues μ1,μ2,…,μn−1,μn=0 and let Sk(G)=∑i=1kμi be the sum of k largest Laplacian eigenvalues of G. Brouwer conjectured that ...Sk(G)≤m+(k+12), for all k=1,2,…,n. We obtain upper bounds for Sk(G), in terms of the clique number ω, the order n and integers p≥0,r≥1,s1≥s2≥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.
Very recently, Aouchiche and Hansen gave an upper bound on the ratio of GA∕χ of the geometric–arithmetic index GA(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 GA(G−e)<GA(G).
Let κ′(G), μn−1(G) and μ1(G) denote the edge-connectivity, the algebraic connectivity and the Laplacian spectral radius of G, respectively. In this paper, we prove that for integers k≥2 and r≥2, and ...any simple graph G of order n with minimum degree δ≥k, girth g≥3 and clique number ω(G)≤r, the edge-connectivity κ′(G)≥k if μn−1(G)≥(k−1)nN(δ,g)(n−N(δ,g)) or if μn−1(G)≥(k−1)nφ(δ,r)(n−φ(δ,r)), where N(δ,g) is the Moore bound on the smallest possible number of vertices such that there exists a δ-regular simple graph with girth g, and φ(δ,r)=max{δ+1,⌊rδr−1⌋}. Analogue results involving μn−1(G) and μ1(G)μn−1(G) to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in Liu et al. (2013) 22, Liu et al. (2019) 20, Hong et al. (2019) 15, Liu et al. (2019) 21 and Abiad et al. (2018) 1 are improved or extended.
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.
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
.
In 1998, Reed conjectured that every graph G satisfies χ(G)≤⌈12(Δ(G)+1+ω(G))⌉, where χ(G) is the chromatic number of G, Δ(G) is the maximum degree of G, and ω(G) is the clique number of G. As ...evidence for his conjecture, he proved an “epsilon version” of it, i.e. that there exists some ε>0 such that χ(G)≤(1−ε)(Δ(G)+1)+εω(G). It is natural to ask if Reed's conjecture or an epsilon version of it is true for the list-chromatic number. In this paper we consider a “local version” of the list-coloring version of Reed's conjecture. Namely, we conjecture that if G is a graph with list-assignment L such that for each vertex v of G, |L(v)|≥⌈12(d(v)+1+ω(v))⌉, where d(v) is the degree of v and ω(v) is the size of the largest clique containing v, then G is L-colorable. Our main result is that an “epsilon version” of this conjecture is true, under some mild assumptions.
Using this result, we also prove a significantly improved lower bound on the density of k-critical graphs with clique number less than k/2, as follows. For every α>0, if ε≤α21350, then if G is an L-critical graph for some k-list-assignment L such that ω(G)<(12−α)k and k is sufficiently large, then G has average degree at least (1+ε)k. This implies that for every α>0, there exists ε>0 such that if G is a graph with ω(G)≤(12−α)mad(G), where mad(G) is the maximum average degree of G, then χℓ(G)≤⌈(1−ε)(mad(G)+1)+εω(G)⌉. It also yields an improvement on the best known upper bound for the chromatic number of Kt-minor free graphs for large t, by a factor of .99982.
Let
be the real field and
be the set of all m × n matrices over
where
For a square matrix
denotes the trace of A (the sum of all diagonal entries of A). The symmetry trace graph
of
is defined to be a ...graph with vertex set of all nonzero matrices in
and two vertices A and B are adjacent if and only if
where
is the transpose of B. Clearly,
is undirected and without loops. In the present paper, by studying maximum cliques of
we determine the form of an arbitrary automorphism of
PDF
