- Tytuł:
- On strongly spanning k-edge-colorable subgraphs
- Autorzy:
-
Mkrtchyan, V. V.
Vardanyan, G. N. - Powiązania:
- https://bibliotekanauki.pl/articles/255490.pdf
- Data publikacji:
- 2017
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
k-edge-colorable subgraph
maximum k-edge-colorable subgraph
trongly spanning k-edge-colorable subgraph
[1, k]-factor. - Opis:
- A subgraph H of a multigraph G is called strongly spanning, if any vertex of G is not isolated in H. H is called maximum k-edge-colorable, if H is proper k-edge-colorable and has the largest size. We introduce a graph-parameter sp(G), that coincides with the smallest k for which a multigraph G has a maximum k-edge-colorable subgraph that is strongly spanning. Our first result offers some alternative definitions of sp(G). Next, we show that Δ (G) is an upper bound for sp(G), and then we characterize the class of multigraphs G that satisfy sp(G) = Δ (G). Finally, we prove some bounds for sp(G) that involve well-known graph-theoretic parameters.
- Źródło:
-
Opuscula Mathematica; 2017, 37, 3; 447-456
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł