Back to Search
Start Over
Cliques in squares of graphs with maximum average degree less than 4.
- Source :
-
Journal of Graph Theory . Jul2024, p1. 19p. 7 Illustrations. - Publication Year :
- 2024
-
Abstract
- Hocquard, Kim, and Pierron constructed, for every even integer D≥2 $D\ge 2$, a 2‐degenerate graph GD ${G}_{D}$ with maximum degree D $D$ such that ω(GD2)=52D $\omega ({G}_{D}^{2})=\frac{5}{2}D$. We prove for (a) all 2‐degenerate graphs G $G$ and (b) all graphs G $G$ with mad(G)<4 $\text{mad}(G)\lt 4$, upper bounds on the clique number ω(G2) $\omega ({G}^{2})$ of G2 ${G}^{2}$ that match the lower bound given by this construction, up to small additive constants. We show that if G $G$ is 2‐degenerate with maximum degree D $D$, then ω(G2)≤52D+72 $\omega ({G}^{2})\le \frac{5}{2}D+72$ (with ω(G2)≤52D+60 $\omega ({G}^{2})\le \frac{5}{2}D+60$ when D $D$ is sufficiently large). And if G $G$ has mad(G)<4 $\text{mad}(G)\lt 4$ and maximum degree D $D$, then ω(G2)≤52D+532 $\omega ({G}^{2})\le \frac{5}{2}D+532$. Thus, the construction of Hocquard et al. is essentially the best possible. Our proofs introduce a “token passing” technique to derive crucial information about nonadjacencies in G $G$ of vertices that are adjacent in G2 ${G}^{2}$. This is a powerful technique for working with such graphs that has not previously appeared in the literature. [ABSTRACT FROM AUTHOR]
- Subjects :
- *INTEGERS
*ADDITIVES
Subjects
Details
- Language :
- English
- ISSN :
- 03649024
- Database :
- Academic Search Index
- Journal :
- Journal of Graph Theory
- Publication Type :
- Academic Journal
- Accession number :
- 178176095
- Full Text :
- https://doi.org/10.1002/jgt.23125