The odd girth of generalized Johnson graphs Caughman, John S.; Herman, Ari J.; Terada, Taiyo S.
Discrete mathematics,
July 2024, 2024-07-00, Letnik:
347, Številka:
7
Journal Article
Recenzirano
For any non-negative integers v>k>i, the generalized Johnson graph, X=J(v,k,i), is the graph whose vertices are the k-subsets of a v-set, and where any two vertices A and B are adjacent whenever ...|A∩B|=i. In this note, we prove that if v≥2k and (v,k,i)≠(2k,k,0), then the odd girth of X is given by:og(X)=2⌈k−iv−2k+2i⌉+1.
Large cycles in generalized Johnson graphs Kozhevnikov, Vladislav; Zhukovskii, Maksim
Journal of graph theory,
December 2023, 2023-12-00, 20231201, Letnik:
104, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We count cycles of an unbounded length in generalized Johnson graphs. Asymptotics of the number of such cycles is obtained for certain growth rates of the cycle length.
•In this paper, we characterize Hamming and Johnson graphs by their spectral gap.•We confirm Babai's conjecture on the motion of distance-regular graphs of bounded diameter.•Our characterization of ...Hamming graphs involves only inequality constraints.
One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with μ≥2 and second largest eigenvalue θ1=b1−1. In this paper we give a classification under the (weaker) approximate eigenvalue constraint θ1≥(1−ε)b1 for the class of geometric distance-regular graphs. As an application, we confirm Babai's conjecture on the minimal degree of the automorphism group of distance-regular graphs of bounded diameter. This conjecture asserts that if X is a primitive distance-regular graph with n vertices, and X is not a Hamming graph or a Johnson graph, then the automorphism group Aut(X) has minimal degree ≥cn for some constant c>0. It follows that Aut(X) satisfies strong structural constraints.
This paper studies thresholds in random generalized Johnson graphs for containing large cycles, i.e. cycles of variable length growing with the size of the graph. Thresholds are obtained for ...different growth rates.
We prove that any completely regular code with minimum eigenvalue in any geometric graph Γ corresponds to a completely regular code in the clique graph of Γ. Studying the interrelation of these ...codes, a complete characterization of the completely regular codes in the Johnson graphs J(n,w) with covering radius w−1 and strength 1 is obtained. In particular this result finishes a characterization of the completely regular codes in the Johnson graphs J(n,3). We also classify the completely regular codes of strength 1 in the Johnson graphs J(n,4) with only one case for the eigenvalues left open.
We prove a conjecture by Van Dam & Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs. More ...generally, we study the smallest eigenvalue and the second largest eigenvalue in absolute value of the graphs of the relations of classical P- and Q-polynomial association schemes.
In the present work we consider the problem of a reconstruction of eigenfunctions of the Johnson graph J(n,w). We give necessary and sufficient numerical conditions for a unique reconstruction of an ...eigenfunction with given eigenvalue by its values on a sphere of given radius r for n big enough. We also provide examples of functions equal on the sphere but not equal on the full vertex set in the case of a failure of these conditions.
•We obtain the upper bounds for the number of edges in even cycle free subgraphs of the doubled Johnson graphs, which are well studied subgraphs of the famous hypercube graphs.•A family of new ...auxiliary graphs related to doubled Johnson graphs are constructed and used in order to obtain the upper bounds.•A new Ramsey type result for doubled Odd graphs is obtained.
The generalized Turán number ex(G,H) is the maximum number of edges in an H-free subgraph of a graph G. It is an important extension of the classical Turán number ex(n,H), which is the maximum number of edges in a graph with n vertices that does not contain H as a subgraph. In this paper, we consider the maximum number of edges in an even-cycle-free subgraph of the doubled Johnson graphs J(n;k,k+1), which are bipartite subgraphs of hypercube graphs. We give an upper bound for ex(J(n;k,k+1),C2r) with any fixed k∈Z+ and any n∈Z+ with n≥2k+1. We also give an upper bound for ex(J(2k+1;k,k+1),C2r) with any k∈Z+, where J(2k+1;k,k+1) is known as doubled Odd graph O˜k+1. This bound induces that the number of edges in any C2r-free subgraph of O˜k+1 is o(e(O˜k+1)) for r≥6, which also implies a Ramsey-type result.
PDF
