• PDF / 269,277 Bytes
• 9 Pages / 439.37 x 666.142 pts Page_size
• 73 Downloads / 239 Views

DOWNLOAD

REPORT

---

(0123456789().,-volV)(0123456789().,-volV)

ORIGINAL PAPER

On Specific Factors in Graphs Csilla Bujta´s1

•

Stanislav Jendrol’2 • Zsolt Tuza3,4

Received: 22 February 2019 / Revised: 22 July 2020  The Author(s) 2020

Abstract It is well known that if G ¼ ðV; EÞ is a connected multigraph and X  V is a subset of even order, then G contains a spanning forest H such that each vertex from X has an odd degree in H and all the other vertices have an even degree in H. This spanning forest may have isolated vertices. If this is not allowed in H, then the situation is much more complicated. In this paper, we study this problem and generalize the concepts of even-factors and odd-factors in a unified form. Keywords Spanning subgraph  Positive factor  Parity factor  Strong parity property

1 Notation and Terminology Let us first present some of the basic definitions, notation and terminology used in this paper. Other terminology will be introduced as it naturally occurs in the text or is used according to West’s book [14]. We denote the vertex set and the edge set of a graph G by V(G) and E(G), respectively. Throughout this paper we use the term graph in the general sense where both loops and multiple edges are allowed, hence cycles of length one (loop) or two (a pair of parallel edges) may also occur. A simple graph is a graph having no loops or multiple edges. The degree of a vertex v, denoted by degG ðvÞ or simply by degðvÞ when the underlying graph is understood, is the number of edges incident with the vertex, where any loop is counted twice. The minimum degree in a graph G will be denoted & Zsolt Tuza [email protected] 1

Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia

2

Institute of Mathematics, P. J. Sˇafa´rik University, Jesenna´ 5, 040 01 Kosˇice, Slovakia

3

Alfre´d Re´nyi Institute of Mathematics, Budapest, Hungary

4

University of Pannonia, Veszpre´m, Hungary

123

Graphs and Combinatorics

by dðGÞ and the maximum degree by DðGÞ. A graph is r-regular if the degree of each vertex in G is r, and the graph is regular if it is r-regular for some r. A set of edges in G is a matching if no two of them share a vertex. A perfect matching (or 1factor) in G is a matching the edges of which span G.

2 Introduction Given a graph G, we shall use the term positive factor for a subgraph H  G if H is a spanning subgraph and has minimum degree dðHÞ  1. A positive factor will also be referred to as a set of edges from G that cover all the vertices of G. We emphasize that in a positive factor all degrees are required to be positive, as opposed to the standard terms of factors and spanning subgraphs. There is a very rich literature concerning factors of graphs, starting with the famous work of Petersen [10]. Several nice survey papers on this subject written by Chung and Graham [3], Akiyama and Kano [1], Volkmann [13], and Plummer [11], and the book of Akiyama and Kano [2] together cover results of over one thousand papers. Beyond the study of 1-factors and 2-factors in regular graphs as i