Edge-connectivity and edge-disjoint spanning trees (Q1011773): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Q3097395 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Edge-connectivity and edge-disjoint spanning trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4873803 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fractional arboricity, strength, and principal partitions in graphs and matroids / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the higher-order edge toughness of a graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5284569 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On n-hamiltonian line graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Eulerian and Hamiltonian Graphs and Line Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3751608 / rank
 
Normal rank

Latest revision as of 11:01, 1 July 2024

scientific article
Language Label Description Also known as
English
Edge-connectivity and edge-disjoint spanning trees
scientific article

    Statements

    Edge-connectivity and edge-disjoint spanning trees (English)
    0 references
    0 references
    0 references
    0 references
    9 April 2009
    0 references
    For a subset \(X\) of edges of a graph \(G\), \(\omega(G-X)\) denotes the number of components of the subgraph \(G-X\). For an integer \(c\) such that \(2\leq c\leq|V(G)|\) the \textit{higher order of edge-connectivity}, \(\lambda_c(G)\), and the \textit{higher order of edge-toughness}, \(\tau_{c-1}(G)\), are defined by \(\lambda_c(G)=\min\{|X|\}\), \(\tau_{c-1}(G)=\min\frac{|X|}{\omega(G-X)-c}\), where the minima are taken over all subsets \(X\subseteq E(G)\) such that \(\omega(G-X)\geq c\) [\textit{C. C. Chen, K. M. Koh} and \textit{Y. H. Peng}, ``On the higher-order edge toughness of a graph'', Discrete Math. 111, No. 1--3, 113--123 (1993; Zbl 0789.05086)]. From the authors' introduction and abstract: ``Over ten years ago Catlin left an unpublished note proving a theorem which characterizes the edge-connectivity of a connected graph \(G\) in terms of the spanning tree packing numbers of its subgraphs. \dots Sadly the author passed away on April 20, 1995. \dots In this paper we establish a relationship between \(\lambda_c(G)\) and \(\tau_{c-1}(G)\) which gives a characterization of the edge-connectivity of a graph \(G\) in terms of the spanning tree packing number of subgraphs of \(G\). The digraph analogue is also obtained. The main results are applied to show that, if a graph \(G\) is \(s\)-hamiltonian, then \(L(G)\) is also \(s\)-hamiltonian, and that, if a graph \(G\) is \(s\)-hamiltonian-connected, then \(L(G)\) is also \(s\)-hamiltonian-connected.''
    0 references
    edge-connectivity
    0 references
    spanning tree packing number
    0 references
    higher order of edge-connectivity
    0 references
    higher order of edge-toughness
    0 references
    \(k\)-arc-connected digraphs
    0 references
    spanning arborescences
    0 references
    line graph
    0 references
    \(s\)-Hamiltonian
    0 references
    \(s\)-Hamiltonian-connected
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references