Iskanje po repozitoriju

Opis: A k-regular graph of girth g is called an edge-girth-regular graph, or an egr-graph for short, if each of its edges is contained in exactly λ distinct g-cycles. An egr-graph is called extremal for the triple (k, g, λ) if has the smallest possible order. We prove that some graphs arising from incidence graphs of finite planes are extremal egr-graphs. We also prove new lower bounds on the order of egr-graphs.
Ključne besede: edge-girth-regular graph, cage problem, finite biaffine planes
Objavljeno v RUP: 03.11.2025; Ogledov: 391; Prenosov: 3
Celotno besedilo (547,76 KB)

Opis: The acyclic number ▫$a(G)$▫ of a graph ▫$G$▫ is the maximum order of an induced forest in ▫$G$▫. The purpose of this short paper is to propose a conjecture that ▫$a(G)\geq \left( 1-\frac{3}{2g}\right)n$▫ holds for every planar graph ▫$G$▫ of girth ▫$g$▫ and order ▫$n$▫, which captures three known conjectures on the topic. In support of this conjecture, we prove a weaker result that ▫$a(G)\geq \left( 1-\frac{3}{g} \right)n$▫ holds. In addition, we give a construction showing that the constant ▫$\frac{3}{2}$▫ from the conjecture cannot be decreased.
Ključne besede: induced forest, acyclic number, planar graph, girth
Objavljeno v RUP: 03.01.2022; Ogledov: 2230; Prenosov: 23
Celotno besedilo (227,50 KB)

Ključne besede: maximal independent set, almost well-covered graph, independence gap, girth
Objavljeno v RUP: 06.12.2018; Ogledov: 3820; Prenosov: 65
Povezava na celotno besedilo

Opis: A complete classification of cubic symmetric graphs of girth 6 is given. It is shown that with the exception of the Heawood graph, the Moebius-Kantor graph, the Pappus graph, and the Desargues graph, a cubic symmetric graph ▫$X$▫ of girth 6 is a normal Cayley graph of a generalized dihedral group; in particular, (i) ▫$X$▫ is 2-regular if and only if it is isomorphic to a so-called ▫$I_k^n$▫-path, a graph of order either ▫$n^2/2$▫ or ▫$n^2/6$▫, which is characterized by the fact that its quotient relative to a certain semiregular automorphism is a path. (ii) ▫$X$▫ is 1-regular if and only if there exists an integer ▫$r$▫ with prime decomposition ▫$r=3^s p_1^{e_1} \dots p_t^{e_t} > 3$▫, where ▫$s \in \{0,1\}$▫, ▫$t \ge 1$▫, and ▫$p_i \equiv 1 \pmod{3}$▫, such that ▫$X$▫ is isomorphic either to a Cayley graph of a dihedral group ▫$D_{2r}$▫ of order ▫$2r$▫ or ▫$X$▫ is isomorphic to a certain ▫$\ZZ_r$▫-cover of one of the following graphs: the cube ▫$Q_3$▫, the Pappus graph or an ▫$I_k^n(t)$▫-path of order ▫$n^2/2$▫.
Ključne besede: graph theory, cubic graphs, symmetric graphs, ▫$s$▫-regular graphs, girth, consistent cycle
Objavljeno v RUP: 15.10.2013; Ogledov: 6424; Prenosov: 96
Povezava na celotno besedilo