Rooted minor problems in highly connected graphs (Q1886348): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2004.07.007 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2081145725 / rank | |||
Normal rank |
Revision as of 03:14, 20 March 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