Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = {x1, . . . , xm} and Y = {y1, . . . , yn} such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for 1 ≤ i ≤ n and G contains Ks,t as a subgraph (resp. the induced subgraph of {x1, . . . , xs, y1, . . . , yt} in G is a Ks,t). In this paper, we give a characterization of L that is potentially As,t-bigraphic. As a corollary, we also obtain a characterization of L that is potentially Ks,t-bigraphic if b1 ≥ b2 ≥ . . . ≥ bm and d1 ≥ d2 ≥ . . . ≥ dn. This is a constructive extension of the characterization on potentially Ks,t-bigraphic pairs due to Yin and Huang (Discrete Math. 312 (2012) 1241–1243).
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this note we consider a discrete symmetric function f(x, y) where $$f(x,a) + f(y,b) \geqslant f(y,a) + f(x,b) for any x \geqslant y and a \geqslant b,$$ associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as $$\sum\limits_{uv \in E(T)} {f(deg(u),deg(v))} ,$$ are characterized by the “greedy tree” and “alternating greedy tree”. This is achieved through simple generalizations of previously used ideas on similar questions. As special cases, the already known extremal structures of the Randic index follow as corollaries. The extremal structures for the relatively new sum-connectivity index and harmonic index also follow immediately, some of these extremal structures have not been identified in previous studies.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.