Cyclic ordering of edges without long acyclic subsequences
Congressus Numerantium · 2025
DOI: 10.61091/cn235-04 ↗Kurz gefasst
Fachartikel in der Zeitschrift Congressus Numerantium, 2025. Verfasst von Yanting Liang und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Let \( G \) be a connected graph with \( m \) edges. The density of a nontrivial subgraph \( H \) with \( \omega(H) \) components is \( d(H) = \frac{|E(H)|}{|V(H)| - \omega(H)} \). A graph \( G \) is uniformly dense if for any nontrivial subgraph \( H \) of \( G \), \( d(H) \leq d(G) \). For each cyclic ordering \( o=(e_1, e_2, \dots, e_m) \) of \( E(G) \), let \( h(o) \) be the largest integer \( k \) such that every \( k \) cyclically consecutive elements in \( o \) induce a forest in \( G \); and the largest \( h(o) \), taken among all cyclic orderings of \( G \), is denoted by \( h(G) \). A cyclic ordering \( o \) of \( G \) is a cyclic base ordering if \( h(o) = |V(G)| - \omega(G) \). In [15], Kajitani et al. proved that every connected nontrivial graph with a cyclic base ordering is uniformly dense, and conjectured that every uniformly dense graph has a cyclic base ordering. This motivates the study of \( h(G) \). In this paper, we investigate the value of \( h \) for some families of graphs and determine all connected graphs \( G \) with \( h(G) \leq 2 \).
Zitieren
APA
Liang, Y., Locke, S., & Trice, A. (2025). Cyclic ordering of edges without long acyclic subsequences. Congressus Numerantium. https://doi.org/10.61091/cn235-04
Vancouver
Liang Y, Locke S, Trice A. Cyclic ordering of edges without long acyclic subsequences. Congressus Numerantium. 2025. doi:10.61091/cn235-04
BibTeX
@article{Liang2025,
author = {Liang, Yanting and Locke, Sarah and Trice, Andrea},
title = {Cyclic ordering of edges without long acyclic subsequences},
journal = {Congressus Numerantium},
year = {2025},
doi = {10.61091/cn235-04}
}
EUVIMED