Girth-regular graphs

DOI10.26493/1855-3974.1684.B0DMaRDI QIDQ5217077zbMATH OpenOpenAlexFDO

Authors Primož Potočnik, Janoš Vidali

Publication date 21 February 2020

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

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

zbMATH Keywords

girthcubicgirth-regular

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: We introduce a notion of a girth-regular graph as a $k$-regular graph for which there exists a non-descending sequence $(a_1,a_2,dots,a_k)$ (called the signature) giving, for every vertex $u$ of the graph, the number of girth cycles the edges with end-vertex $u$ lie on. Girth-regularity generalises two very different aspects of symmetry in graph theory: that of vertex transitivity and that of distance-regularity. For general girth-regular graphs, we give some results on the extremal cases of signatures. We then focus on the cubic case and provide a characterisation of cubic girth-regular graphs of girth up to $5$.

Recommendations

• A stability result for girth‐regular graphs with even girth
• Extremal edge-girth-regular graphs
• On girth-biregular graphs
• Edge-girth-regular graphs
• Symmetric cubic graphs of small girth

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3432305 (Why is no real title available?)
• scientific article; zbMATH DE number 3412694 (Why is no real title available?)
• A census of semisymmetric cubic graphs on up to 768 vertices
• A complete classification of cubic symmetric graphs of girth 6
• Cubic vertex-transitive graphs on up to 1280 vertices
• Edge-girth-regular graphs
• Finite generalized quadrangles
• On generalized hexagons and a near octagon whose lines have three points
• Sur la trialité et certains groupes qui s'en déduisent
• Symmetric cubic graphs of small girth
• Symmetry properties of generalized graph truncations
• Tetravalent edge-transitive graphs of girth at most 4
• The nonexistence of certain generalized polygons

Cited in

(22)

• r-regular r-connected graphs with large girth
• DiscreteZOO: a fingerprint database of discrete objects
• Locally bi-2-transitive graphs and cycle-regular graphs, and the answer to a 2001 problem posed by Fouquet and Hahn
• Finite cubic graphs admitting a cyclic group of automorphism with at most three orbits on vertices
• Edge-girth-regular graphs
• Extremal edge-girth-regular graphs
• scientific article; zbMATH DE number 1833089 (Why is no real title available?)
• Edge-transitive bi-Cayley graphs
• A characterization of tetravalent half-arc-transitive graphs of girth 5
• On orders of automorphisms of vertex-transitive graphs
• An infinite family of simple graphs underlying chiral, orientable reflexible and non-orientable rotary maps
• On vertex-girth-regular graphs: (non-)existence, bounds and enumeration
• Cubic vertex-transitive graphs admitting automorphisms of large order
• On the number of fixed points of automorphisms of vertex-transitive graphs
• Cubic vertex-transitive graphs of girth six
• A stability result for girth‐regular graphs with even girth
• On girth-biregular graphs
• Tight factorizations of girth-3-regular graphs
• Restrictions on girths in compact graphs
• Classification of cubic vertex-transitive tricirculants
• On extremal (almost) edge-girth-regular graphs
• On cubic rainbow domination regular graphs

This page was built for publication: Girth-regular graphs

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