2016/10/19 by Matthew W. Ashford, Ashford, Matthew
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Mathematics and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1610.06021
openalex publication_date 2016/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A kei on [n] can be thought of as a set of maps (fx)x ∈ [n], where each fx is an involution on [n] such that (x)fx = x for all x and f(x)fy = fyfxfy for all x and y. We can think of kei as loopless, edge-coloured multigraphs on [n] where we have an edge of colour y between x and z if and only if (x)fy = z; in this paper we show that any component of diameter d in such a graph must have at least 2d vertices and contain at least 2d-1 edges of the same colour. We also show that these bounds are tight for each value of d.