On Vertex-Disjoint Triangles in Tripartite Graphs and Multigraphs
- PDF / 270,921 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 208 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
On Vertex-Disjoint Triangles in Tripartite Graphs and Multigraphs Qingsong Zou1
•
Jiawang Li1 • Zizheng Ji1
Received: 17 October 2018 / Revised: 21 April 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Let G be a tripartite graph with tripartition ðV1 ; V2 ; V3 Þ, where j V1 j¼j V2 j¼j V3 j¼ k [ 0. It is proved that if dðxÞ þ dðyÞ 3k for every pair of nonadjacent vertices x 2 Vi ; y 2 Vj with i 6¼ jði; j 2 f1; 2; 3gÞ, then G contains k vertex-disjoint triangles. As a corollary, if dðxÞ 32 k for each vertex x 2 VðGÞ, then G contains k vertex-disjoint triangles. Based on the above results, vertexdisjoint triangles in multigraphs are studied. Let M be a standard tripartite multigraph with tripartition ðV1 ; V2 ; V3 Þ, where j V1 j¼j V2 j¼j V3 j¼ k [ 0. If dðMÞ 3k 1 for even k and dðMÞ 3k for odd k, then M contains k vertex-disjoint 4-triangles D4 (a triangle with at least four edges). Furthermore, examples are given showing that the degree conditions of all our three results are best possible. Keywords Tripartite graphs Multigraphs Triangles Cycles Vertex-disjoint
Mathematics Subject Classification 05C38 05C70
1 Introduction Graphs considered here are finite undirected graphs without loops. For a graph G ¼ ðVðGÞ; EðGÞ; wG Þ, we use V(G), E(G), dðGÞ, aðGÞ to denote the vertex set, edge set, the minimum degree and the independence number of G respectively. The order of G is j G j and its size is j EðGÞ j. For two vertices x; y 2 VðGÞ, lðx; yÞ is the number of edges connecting x and y in G. Particularly, lðx; yÞ ¼ 0 if xy 62 EðGÞ. Let This work was supported by National Natural Science Foundation of Shaanxi Province (Grant no. 2020JM-199) and National Natural Science Foundation of China (Grant no. 11401455) & Qingsong Zou [email protected] 1
School of Mathematics and Statistics, Xidian University, Xi’an 710071, People’s Republic of China
123
Graphs and Combinatorics
lðGÞ ¼ maxx;y2VðGÞ lðx; yÞ. A simple graph is a graph G with lðGÞ 1, and a multigraph is a graph M with lðMÞ 2. For an integer t 1, we define rt ðGÞ ¼ P minf v2X dðvÞjX is an independent set of G with jXj ¼ tg, and rt ðGÞ ¼ 1 when aðGÞ\t. A k-cycle is a cycle of order k and an m-path is a path of order m, denoted by C k and Pm respectively. In particular, a triangle is a cycle of order 3, and a quadrilateral is a cycle of order 4. For a k-cycle C ¼ x1 x2 . . .xk x1 , xi xiþ1 (1 i k T 1) and xk x1 are edges in C. Given a subgraph H of G, we write NH ðxÞ ¼ NG ðxÞ VðHÞ, and dH ðxÞ ¼j NH ðxÞ j. Let X and Y be two vertex-disjoint subgraphs of G or two disjoint subsets of V(G), then G[X] is the subgraph of G induced by X, and e(X, Y) is equal to the number of edges between X and Y. For a simple graph T, G kT means that G contains k vertex-disjoint subgraphs isomorphic to T. Unexplained notation and terminology are adopted from [1]. In the following, a simple graph is denoted by a graph for simplicity. One of the outstanding result on cycles come
Data Loading...
