We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Vertex-Disjoint Quadrilaterals in Multigraphs.
- Authors
Gao, Yunshu; Zou, Qingsong; Ma, Liyan
- Abstract
A cycle of length four is called a quadrilateral and a multigraph is called standard if every edge in it has multiplicity at most two. We prove that if M is a standard multigraph of order 4 k, where k is a positive integer and the minimum degree of M is at least $$6k-2$$ , then M contains k vertex-disjoint quadrilaterals, such that each quadrilateral contains at least three multiedges, with only two exceptions. This implies the main result obtained by Zhang and Wang [J Graph Theory 50:91-104, 2005]: Let D be a directed graph of order 4 k, where k is a positive integer. Suppose that the minimum degree of D is at least $$6k-2$$ , then D contains k vertex-disjoint directed quadrilaterals with only one exception.
- Subjects
GEOMETRIC vertices; QUADRILATERALS; MULTIGRAPH; INTEGERS; ARBITRARY constants
- Publication
Graphs & Combinatorics, 2017, Vol 33, Issue 4, p901
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-017-1811-6