
doi: 10.7151/dmgt.2375
Summary: Let \(\pi=(f_1,\dots,f_m;g_1,\dots,g_n)\), where \(f_1,\dots,f_m\) and \(g_1,\dots,g_n\) are two non-increasing sequences of nonnegative integers. The pair \(\pi=(f_1,\dots,f_m; g_1,\dots,g_n)\) is said to be a bigraphic pair if there is a simple bipartite graph \(G=(X\cup Y,E)\) such that \(f_1,\dots,f_m\) and \(g_1,\dots,g_n\) are the degrees of the vertices in \(X\) and \(Y\), respectively. In this case, \(G\) is referred to as a realization of \(\pi \). We say that \(\pi\) is a potentially \(K_{s,t}\)-bigraphic pair if some realization of \(\pi\) contains \(K_{s,t}\) (with \(s\) vertices in the part of size \(m\) and \(t\) in the part of size \(n)\). \textit{M. Ferrara} et al. [ibid. 29, No. 3, 583--596 (2009; Zbl 1194.05022)] defined \(\sigma(K_{s,t},m,n)\) to be the minimum integer \(k\) such that every bigraphic pair \(\pi=(f_1,\dots,f_m;g_1,\dots,g_n)\) with \(\sigma(\pi)=f_1+\cdots +f_m\ge k\) is potentially \(K_{s,t}\)-bigraphic. They determined \(\sigma(K_{s,t},m,n)\) for \(n\ge m\ge 9s^4t^4\). In this paper, we first give a procedure and two sufficient conditions to determine if \(\pi\) is a potentially \(K_{s,t}\)-bigraphic pair. Then, we determine \(\sigma(K_{s,t}, m,n)\) for \(n\ge m\ge s\) and \(n\ge (s+1)t^2-(2s-1)t+s-1\). This provides a solution to a problem due to Ferrara et al. [loc. cit.].
Extremal problems in graph theory, realization, potentially \(K_{s,t}\)-bigraphic pair, QA1-939, Vertex degrees, Mathematics, bigraphic pair
Extremal problems in graph theory, realization, potentially \(K_{s,t}\)-bigraphic pair, QA1-939, Vertex degrees, Mathematics, bigraphic pair
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
