Independence numbers of Johnson-type graphs

2019/07/15 by Danila Cherkashin, Cherkashin, Danila, С. В. Киселев +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1907.06752

openalex publication_date 2019/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a family of distance graphs in ℝⁿ and find its independent numbers in some cases. Define graph J_±(n,k,t) in the following way: the vertex set consists of all vectors from \-1,0,1\ⁿ with k nonzero coordinates; edges connect the pairs of vertices with scalar product t. We find the independence number of J_±(n,k,t) for n > n₀ (k,t) in the cases t = 0 and t = -1; these cases for k = 3 are solved completely. Also the independence number is found for negative odd t and n > n₀ (k,t).

Cited by

• On the chromatic numbers of Johnson type graphs

Related

• Lower bounds on the independence numbers of distance graphs with vertices in \-1, 0, 1\ⁿ
• Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree
• On the k-independence number of graph products
• Unified bounds for the independence number of graph powers
• On inertia and ratio type bounds for the k-independence number of a graph and their relationship