Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 36 min ago
PreprintCC BY 4.0arXiv

On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs

  • Elizaveta Popova
Open at sourcePDFDOICite

Abstract

The following is a natural and fundamental question for a graph G: if an induced subgraph H of G has x more vertices than a maximum independent set, what can be said about the maximum degree of H as a function of x? The case x=1 is already of considerable interest. For example, in his celebrated proof of the sensitivity conjecture, Hao Huang showed that every induced subgraph of the hypercube Qn on more than 2n−1 vertices has maximum degree at least √n. Chung, Fúredi, Graham, and Seymour proved that this bound is tight. In this paper, we study this question when G is either the n-fold Hamming product or the n-fold tensor product of a triangle. For both graphs, we determine the exact minimum possible average degree of an induced subgraph of a prescribed size. We also prove that the tensor product exhibits several Huang-like phenomena. For the Hamming product, we show that, for several size densities and large n, the minimum possible maximum degree is asymptotically equal to the minimum possible average degree. Finally, we extend several of the results from the triangle to an arbitrary complete graph Kk.

Related

  1. Large induced subgraphs with k vertices of maximum degree
    Zhen liu, Qinghou Zeng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees
    Yonglei Chen, Yan Cao
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. A Sublinear Minimum-Degree Condition for $2$-Connected Subgraphs of All Orders
    Kenta Ozeki, Takahiro Ueoro
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Small subgraphs of large minimum degree
    Zach Hunter, Barnabás Janzer, Oliver Janzer +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Minimum Distance Spectral Radius of Tree with Given Maximum Degree
    Yifei Li, Zia Ullah Khan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{popova2026minimum,
  title = {{On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs}},
  author = {Elizaveta Popova},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.32903},
  eprint = {2609.32903},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.32903},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs
AU  - Elizaveta Popova
PY  - 2026
DA  - 2026/09/26
PB  - arXiv
DO  - 10.48550/arxiv.2609.32903
UR  - https://arxiv.org/abs/2609.32903
AB  - The following is a natural and fundamental question for a graph G: if an induced subgraph H of G has x more vertices than a maximum independent set, what can be said about the maximum degree of H as a function of x? The case x=1 is already of considerable interest. For example, in his celebrated proof of the sensitivity conjecture, Hao Huang showed that every induced subgraph of the hypercube Q_n on more than 2^n−1 vertices has maximum degree at least √n. Chung, Fúredi, Graham, and Seymour proved that this bound is tight. In this paper, we study this question when G is either the n-fold Hamming product or the n-fold tensor product of a triangle. For both graphs, we determine the exact minimum possible average degree of an induced subgraph of a prescribed size. We also prove that the tensor product exhibits several Huang-like phenomena. For the Hamming product, we show that, for several size densities and large n, the minimum possible maximum degree is asymptotically equal to the minimum possible average degree. Finally, we extend several of the results from the triangle to an arbitrary complete graph K_k.
ER  -