On the girth and diameter of generalized Johnson graphs
| Autor: | Carmen Amarra, John S. Caughman, Ari J. Herman, Louis Anthony Agong, Taiyo S. Terada |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Johnson graph Induced path 010102 general mathematics 0102 computer and information sciences 01 natural sciences Graph Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Chordal graph Odd graph Discrete Mathematics and Combinatorics Graph homomorphism 0101 mathematics Cage Mathematics Moore graph |
| Zdroj: | Discrete Mathematics. 341:138-142 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2017.08.022 |
| Popis: | Let v > k > i be non-negative integers. The generalized Johnson graph, J ( v , k , i ) , is the graph whose vertices are the k -subsets of a v -set, where vertices A and B are adjacent whenever | A ∩ B | = i . In this article, we derive general formulas for the girth and diameter of J ( v , k , i ) . Additionally, we provide a formula for the distance between any two vertices A and B in terms of the cardinality of their intersection. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect