We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On Vertex-Disjoint Triangles in Tripartite Graphs and Multigraphs.
- Authors
Zou, Qingsong; Li, Jiawang; Ji, Zizheng
- Abstract
Let G be a tripartite graph with tripartition (V 1 , V 2 , V 3) , where ∣ V 1 ∣ = ∣ V 2 ∣ = ∣ V 3 ∣ = k > 0 . It is proved that if d (x) + d (y) ≥ 3 k for every pair of nonadjacent vertices x ∈ V i , y ∈ V j with i ≠ j (i , j ∈ { 1 , 2 , 3 }) , then G contains k vertex-disjoint triangles. As a corollary, if d (x) ≥ 3 2 k for each vertex x ∈ V (G) , then G contains k vertex-disjoint triangles. Based on the above results, vertex-disjoint triangles in multigraphs are studied. Let M be a standard tripartite multigraph with tripartition (V 1 , V 2 , V 3) , where ∣ V 1 ∣ = ∣ V 2 ∣ = ∣ V 3 ∣ = k > 0 . If δ (M) ≥ 3 k - 1 for even k and δ (M) ≥ 3 k for odd k, then M contains k vertex-disjoint 4-triangles Δ 4 (a triangle with at least four edges). Furthermore, examples are given showing that the degree conditions of all our three results are best possible.
- Subjects
TRIANGLES; MULTIGRAPH; EDGES (Geometry)
- Publication
Graphs & Combinatorics, 2020, Vol 36, Issue 5, p1355
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-020-02188-3