Loading...
Loading...

Go to the content (press return)

On the acyclic disconnection and the girth

Author
Balbuena, C.; Olsen, M.
Type of activity
Journal article
Journal
Discrete applied mathematics
Date of publication
2015-05-11
Volume
186
First page
13
Last page
18
DOI
https://doi.org/10.1016/j.dam.2015.01.025 Open in new window
Project funding
Control de invariantes en grafos sujetos a propiedades estructurales
Repository
http://hdl.handle.net/2117/86820 Open in new window
URL
http://www.sciencedirect.com/science/article/pii/S0166218X1500027X Open in new window
Abstract
The acyclic disconnection, (omega) over right arrow (D), of a digraph D is the maximum number of connected components of the underlying graph of D - A(D*), where D* is an acyclic subdigraph of D. We prove that (omega) over right arrow (D) >= g - 1 for every strongly connected digraph with girth g >= 4, and we show that (omega) over right arrow (D) = g - 1 if and only if D congruent to C-g for g >= 5. We also characterize the digraphs that satisfy (omega) over right arrow (D) = g - 1, for g = 4 i...
Citation
Balbuena, C., Olsen, M. On the acyclic disconnection and the girth. "Discrete applied mathematics", 11 Maig 2015, vol. 186, p. 13-18.
Keywords
Acyclic disconnection, Digraphs, Girth, Projective planes, Semigirth, Tournaments
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants

Attachments