Geodesic
Spanning \(k\)-trees of bipartite graphs
Mikio Kano1 ; Kenta Ozeki2 ; Kazuhiro Suzuki3 ; Masao Tsugaki4 ; Tomoki Yamashita5
1Ibaraki University
2National Institute of Informatics
3Kochi University
4Chinese Academy of Science
5Kinki University
The electronic journal of combinatorics, Tome 22 (2015) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A tree is called a $k$-tree if its maximum degree is at most $k$. We prove the following theorem. Let $k \geq 2$ be an integer, and $G$ be a connected bipartite graph with bipartition $(A,B)$ such that $|A| \le |B| \le (k-1)|A|+1$. If $\sigma_k(G) \ge |B|$, then $G$ has a spanning $k$-tree, where $\sigma_k(G)$ denotes the minimum degree sum of $k$ independent vertices of $G$. Moreover, the condition on $\sigma_k(G)$ is sharp. It was shown by Win (Abh. Math. Sem. Univ. Hamburg, 43, 263–267, 1975) that if a connected graph $H$ satisfies $\sigma_k(H) \ge |H|-1$, then $H$ has a spanning $k$-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.
DOI : 10.37236/3628
Classification : 05C05, 05C70
Mots-clés : spanning tree, spanning \(k\)-tree, bipartite graph

Mikio Kano  1   ; Kenta Ozeki  2   ; Kazuhiro Suzuki  3   ; Masao Tsugaki  4   ; Tomoki Yamashita  5

1 Ibaraki University
2 National Institute of Informatics
3 Kochi University
4 Chinese Academy of Science
5 Kinki University 
@article{10_37236_3628,
     author = {Mikio Kano and Kenta Ozeki and Kazuhiro Suzuki and Masao Tsugaki and Tomoki Yamashita},
     title = {Spanning \(k\)-trees of bipartite graphs},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {1},
     doi = {10.37236/3628},
     zbl = {1305.05046},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3628/}
}
TY  - JOUR
AU  - Mikio Kano
AU  - Kenta Ozeki
AU  - Kazuhiro Suzuki
AU  - Masao Tsugaki
AU  - Tomoki Yamashita
TI  - Spanning \(k\)-trees of bipartite graphs
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3628/
DO  - 10.37236/3628
ID  - 10_37236_3628
ER  - 
%0 Journal Article
%A Mikio Kano
%A Kenta Ozeki
%A Kazuhiro Suzuki
%A Masao Tsugaki
%A Tomoki Yamashita
%T Spanning \(k\)-trees of bipartite graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3628/
%R 10.37236/3628
%F 10_37236_3628
Mikio Kano; Kenta Ozeki; Kazuhiro Suzuki; Masao Tsugaki; Tomoki Yamashita. Spanning \(k\)-trees of bipartite graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/3628

Cité par Sources :