About an extremal problem of bigraphic pairs with a realization containing Ks, t
About an extremal problem of bigraphic pairs with a realization containing Ks, t
复制标题
DOI：
10.7151/dmgt.2375
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Jianhua Yin;Bing Wang
中科院分区：
文献类型：
--
作者：
Jianhua Yin;Bing Wang
设π =（f1，. . .，fm; g1，. . .，gn），其中f1，. . .，fm和g1，. . .，gn是两个非负整数的非增序列。对π =（f1，. . .，fm; g1，. . .，gn）称为偶图对，如果存在简单偶图G =（X <$Y，E）使得f1，. . .，fm和g1，. . .，gn分别是X和Y中的顶点的度数。在这种情况下，G被称为π的实现。我们说π是一个潜在的Ks，t-双图对，如果π的某个实现包含Ks，t（s个顶点在大小为m的部分，t个顶点在大小为n的部分）。费拉拉等人[潜在的H-双图序列，讨论。Math. GraphTheory 29（2009）583-596]定义σ（Ks，t，m，n）为最小整数k，使得每个双图对π =（f1，. . .，fm; g1，. . .，gn），其中σ（π）= f1+· · ·+fm ≥ k，是可能Ks，t-双图的.确定了σ（Ks，t，m，n），其中n ≥ m ≥ 9 st。本文首先给出了判定π是一个潜在Ks，t-双图对的一个步骤和两个充分条件。然后，我们确定σ（Ks，t，m，n），其中n ≥ m ≥ s且n ≥（s+ 1）t−（2s− 1）t+ s− 1。这提供了对由于费拉拉等人的问题的解决方案。
Let π = (f1, . . . , fm; g1, . . . , gn), where f1, . . . , fm and g1, . . . , gn are two non-increasing sequences of nonnegative integers. The pair π = (f1, . . . , fm; g1, . . . , gn) is said to be a bigraphic pair if there is a simple bipartite graph G = (X ∪ Y,E) such that f1, . . . , fm and g1, . . . , gn are the degrees of the vertices in X and Y , respectively. In this case, G is referred to as a realization of π. We say that π is a potentially Ks,t-bigraphic pair if some realization of π contains Ks,t (with s vertices in the part of size m and t in the part of size n). Ferrara et al. [Potentially H-bigraphic sequences, Discuss. Math. Graph Theory 29 (2009) 583–596] defined σ(Ks,t,m, n) to be the minimum integer k such that every bigraphic pair π = (f1, . . . , fm; g1, . . . , gn) with σ(π) = f1+· · ·+fm ≥ k is potentiallyKs,t-bigraphic. They determined σ(Ks,t,m, n) for n ≥ m ≥ 9st. In this paper, we first give a procedure and two sufficient conditions to determine if π is a potentially Ks,t-bigraphic pair. Then, we determine σ(Ks,t,m, n) for n ≥ m ≥ s and n ≥ (s+ 1)t− (2s− 1)t+ s− 1. This provides a solution to a problem due to Ferrara et al.