Rooted minor problems in highly connected graphs (Q1886348): Difference between revisions
From MaRDI portal
Latest revision as of 15:20, 7 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Rooted minor problems in highly connected graphs |
scientific article |
Statements
Rooted minor problems in highly connected graphs (English)
0 references
18 November 2004
0 references
A graph is said to have a rooted complete bipartite minor \(K_{a,k}\) if for every \(k\) distinct vertices \(v_1,\dots,v_k\) there are disjoint connected subgraphs \(H_1,\dots, H_a, K_1,\dots, K_k\) such that each of the \(K_i\) contains \(v_i\) and is adjacent to all \(H_1,\dots,H_a\). The author derives connectivity conditions for the existence of rooted complete bipartite minors from some known and deep connectivity or average degree conditions for the existence of (non-rooted) complete bipartite minors. Among others it is proved that for every \(a\) there is a constant \(N(a)\) such that every \(25k\)-connected graph of order at least \(N(a)\) has a rooted complete bipartite minor \(K_{a,k}\).
0 references
rooted minor
0 references
connectivity
0 references