Mixed cages: monotonicity, connectivity and upper bounds

DOI10.1016/J.DISC.2021.112792zbMATH Open1484.05114arXiv2009.13709OpenAlexW4229077714MaRDI QIDQ2113343FDOQ2113343

Authors: G. Araujo-Pardo, Claudia De la Cruz, Diego González-Moreno 

Publication date: 14 March 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A emph{$[z,r;g]$-mixed cage} is a mixed graph $z$-regular by arcs, $r$-regular by edges, with girth $g$ and minimum order. %In this paper we study structural properties of mixed cages: Let $n[z,r;g]$ denote the order of a $[z,r;g]$-mixed cage. In this paper we prove that $n[z,r;g]$ is a monotonicity function, with respect of $g$, for $zin1,2$, and we use it to prove that the underlying graph of a $[z,r;g]$-mixed cage is 2-connected, for $zin1,2$. We also prove that $[z,r;g]$-mixed cages are strong connected. We present bounds of $n[z,r;g]$ and constructions of $[z,r;5]$-mixed graphs and show a $[10,3;5]$-mixed cage of order $50$.

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

Recommendations

• Mixed cages
• Monotonicity of the order of \((D;g)\)-cages
• On upper bounds and connectivity of cages
• An improved upper bound for the order of mixed graphs
• New results on connectivity of cages

zbMATH Keywords

monotonicityprojective planesconnectivitycages and directed cagesmixed cages

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Finite affine and projective planes (geometric aspects) (51E15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Dynamic cage survey
• Title not available (Why is that?)
• On Hamiltonian Regular Graphs of Girth Six
• Girth 5 graphs from elliptic semiplanes
• Families of small regular graphs of girth 5
• A family of mixed graphs with large order and diameter 2
• A note on the edge-connectivity of cages
• Connectivity of cages
• All (k;g)-cages arek-edge-connected
• On the connectivity of \((k,g)\)-cages of even girth
• A new bound for the connectivity of cages
• New small regular graphs of girth 5
• Mixed cages

Cited In (4)

• Mixed cages
• Edge-girth-regular graphs arising from biaffine planes and Suzuki groups
• A note on the edge-connectivity of cages
• On new record graphs close to bipartite Moore graphs

This page was built for publication: Mixed cages: monotonicity, connectivity and upper bounds

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