Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph

DOI10.4213/sm10021eMaRDI QIDQ6639684

Yakov K. Shubin, Nikita A. Dubinin, A. M. Raigorodskii, Elizaveta A. Neustroeva

Publication date: 18 November 2024

Published in: Sbornik: Mathematics (Search for Journal in Brave)

zbMATH Keywords

extremal graph theoryJohnson graphsdistance graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Distance in graphs (05C12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intersection theorems with geometric consequences
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• On the minimal number of edges in induced subgraphs of special distance graphs
• Estimate of the number of edges in special subgraphs of a distance graph
• On stability of the independence number of a certain distance graph
• The number of edges in induced subgraphs of some distance graphs
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• A counterexample to Borsuk’s conjecture
• Graphs with maximal number of adjacent pairs of edges
• On the Shannon capacity of a graph
• Sharp threshold for the Erdős–Ko–Rado theorem
• Intersection theorems for \((- 1, 0, 1)\)-vectors
• Estimates of the Number of Edges in Subgraphs of Johnson Graphs

This page was built for publication: Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph