Opuscula Math. 37, no. 3 (2017), 435-446
http://dx.doi.org/10.7494/OpMath.2017.37.3.435
Opuscula Mathematica
On strongly spanning k-edge-colorable subgraphs
Vahan V. Mkrtchyan
Gagik N. Vardanyan
Abstract. 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 \(\Delta(G)\) is an upper bound for \(sp(G)\), and then we characterize the class of multigraphs \(G\) that satisfy \(sp(G)=\Delta(G)\). Finally, we prove some bounds for \(sp(G)\) that involve well-known graph-theoretic parameters.
Keywords: \(k\)-edge-colorable subgraph, maximum \(k\)-edge-colorable subgraph, strongly spanning \(k\)-edge-colorable subgraph, \([1,k]\)-factor.
Mathematics Subject Classification: 05C70, 05C15.
- Vahan V. Mkrtchyan
- Yerevan State University, Department of Informatics and Applied Mathematics, Yerevan, 0025, Armenia
- National Academy of Sciences of Republic of Armenia, Institute for Informatics and Automation Problems, 0014, Armenia
- Gagik N. Vardanyan
- Yerevan State University, Department of Informatics and Applied Mathematics, Yerevan, 0025, Armenia
- Received: 2015-12-03.
- Revised: 2016-09-15.
- Accepted: 2016-09-29.
Cite this article as:
Vahan V. Mkrtchyan, Gagik N. Vardanyan, On strongly spanning k-edge-colorable subgraphs, Opuscula Math. 37, no. 3 (2017), 435-446, http://dx.doi.org/10.7494/OpMath.2017.37.3.435
Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.