Graphs whose Kronecker covers are bipartite Kneser graphs

DOI10.1016/J.DISC.2020.112264MaRDI QIDQ2659178zbMATH OpenOpenAlexFDO

Authors Takahiro Matsushita

Publication date 25 March 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.09051

zbMATH Keywords

automorphism groups of graphsbipartite Kneser graphschromatic numbersKneser graphsKronecker coversneighborhood complexes

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We show that there are $k$ simple graphs whose Kronecker covers are isomorphic to the bipartite Kneser graph $H(n,k)$, and that their chromatic numbers coincide with $chi(K(n,k))=n-2k+2$. We also determine the automorphism groups of these graphs.

Review text

The author investigates graphs whose Kronecker cover are equal to the Kronecker cover of a Kneser graph. The Kronecker cover \(K_2\times K(n,k)\) of a Kneser graph is bipartite and also called a bipartite Kneser graph. It is denoted by \(H(n,k)\). Graphs with isomorphic Kronecker covers need not to be isomorphic but share many common properties in general. Here, the author constructs \(k\) distinct pairwise non-isomorphic graphs that all have \(H(n,k)\) as their Kronecker cover for every \(n, k\) with \(n > 2k\), \(k \geq 1\). He shows that all these graphs have the same chromatic number as the Kneser graph \(K(n,k)\). Furthermore, he studies the automorphism group of these graphs.

Recommendations

• Neighborhood complexes and Kronecker double coverings
• Generalized Petersen graphs and Kronecker covers
• Multiple Kronecker covering graphs
• The automorphism group of the bipartite Kneser graph
• Some algebraic properties of bipartite Kneser graphs.

Cites work

• Bipartite Kneser graphs are Hamiltonian
• Combinatorial algebraic topology
• Double covers of graphs
• Erdős-Ko-Rado theorems. Algebraic approaches
• Generalized Petersen graphs and Kronecker covers
• scientific article; zbMATH DE number 2133100 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• Hypercubes As Direct Products
• Kneser's conjecture, chromatic number, and homotopy
• Kronecker covers, V-construction, unit-distance graphs and isometric point-circle configurations
• Multiple Kronecker covering graphs
• Neighborhood hypergraphs of bipartite graphs
• Proof of the middle levels conjecture
• The automorphism group of the bipartite Kneser graph

Cited in

(10)

• Neighborhood complexes and Kronecker double coverings
• The automorphism group of the bipartite Kneser graph
• Automorphism groups of some families of bipartite graphs
• Some algebraic properties of bipartite Kneser graphs.
• Generalized Petersen graphs and Kronecker covers
• Some new classes of distance integral graphs constructed from integral graphs
• Some conditions implying stability of graphs
• Characterization of generalised Petersen graphs that are Kronecker covers
• Dominance complexes, neighborhood complexes and combinatorial Alexander duals
• Multiple Kronecker covering graphs

This page was built for publication: Graphs whose Kronecker covers are bipartite Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2659178)