EUVIMEDEUVIMED entdecken
Crossref

Cyclic ordering of edges without long acyclic subsequences

Yanting Liang, Sarah Locke, Andrea Trice

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →