Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe clique number and the smallest Q-eigenvalue of graphs
127
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $q_{min}(G)$ stand for the smallest eigenvalue of the signless Laplacian of a graph $G$ of order $n.$ This paper gives some results on the following extremal problem: How large can $q_minleft( Gright) $ be if $G$ is a graph of order $n,$ with no complete subgraph of order $r+1?$ It is shown that this problem is related to the well-known topic of making graphs bipartite. Using known classical results, several bounds on $q_{min}$ are obtained, thus extending previous work of Brandt for regular graphs. In addition, using graph blowups, a general asymptotic result about the maximum $q_{min}$ is established. As a supporting tool, the spectra of the Laplacian and the signless Laplacian of blowups of graphs are calculated.
rate research
Read More
Given a graph $G$, the strong clique number of $G$, denoted $omega_S(G)$, is the maximum size of a set $S$ of edges such that every pair of edges in $S$ has distance at most $2$ in the line graph of $G$. As a relaxation of the renowned ErdH{o}s--Nev{s}etv{r}il conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if $G$ is a $C_{2k}$-free graph, then $omega_S(G)leq (2k-1)Delta(G)-{2k-1choose 2}$, and if $G$ is a $C_{2k}$-free bipartite graph, then $omega_S(G)leq kDelta(G)-(k-1)$. We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a ${C_5, C_{2k}}$-free graph $G$ with $Delta(G)ge 1$ satisfies $omega_S(G)leq kDelta(G)-(k-1)$, when either $kgeq 4$ or $kin {2,3}$ and $G$ is also $C_3$-free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for $kgeq 3$, we prove that a $C_{2k}$-free graph $G$ with $Delta(G)ge 1$ satisfies $omega_S(G)leq (2k-1)Delta(G)+(2k-1)^2$. This improves some results of Cames van Batenburg, Kang, and Pirot.
In this paper, we give a combinatorial characterization of the special graphs of fat Hoffman graphs containing $mathfrak{K}_{1,2}$ with smallest eigenvalue greater than -3, where $mathfrak{K}_{1,2}$ is the Hoffman graph having one slim vertex and two fat vertices.
Koolen et al. showed that if a graph with smallest eigenvalue at least $-3$ has large minimal valency, then it is $2$-integrable. In this paper, we will focus on the sesqui-regular graphs with smallest eigenvalue at least $-3$ and study their integrability.
We investigate fat Hoffman graphs with smallest eigenvalue at least -3, using their special graphs. We show that the special graph S(H) of an indecomposable fat Hoffman graph H is represented by the standard lattice or an irreducible root lattice. Moreover, we show that if the special graph admits an integral representation, that is, the lattice spanned by it is not an exceptional root lattice, then the special graph S(H) is isomorphic to one of the Dynkin graphs A_n, D_n, or extended Dynkin graphs A_n or D_n.
In this paper, we show that all fat Hoffman graphs with smallest eigenvalue at least -1-tau, where tau is the golden ratio, can be described by a finite set of fat (-1-tau)-irreducible Hoffman graphs. In the terminology of Woo and Neumaier, we mean that every fat Hoffman graph with smallest eigenvalue at least -1-tau is an H-line graph, where H is the set of isomorphism classes of maximal fat (-1-tau)-irreducible Hoffman graphs. It turns out that there are 37 fat (-1-tau)-irreducible Hoffman graphs, up to isomorphism.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
