Abstract. Determining the maximum number of edges in an intersecting hypergraph on a fixed ground set under additional constraints is one of the central topics in extremal combinatorics. In contrast, there are few results on analogous problems concerning the maximum order of such hypergraphs. In this paper, we systematically study these vertex analogues.

We characterize the bipartite graphs that minimize the (first degree-based) entropy among all bipartite graphs of given size. For bipartite graphs given size and (upper bound on the) order, we give a lower bound for this entropy. The extremal graphs turn out to be complete bipartite graphs, or nearly complete bipartite. Here we make use of an equivalent representation of bipartite graphs by means of Young diagrams, which make it easier to compare the entropy of related graphs. We conclude that the general characterization of the extremal graphs is a difficult problem, due to its connections with number theory. However, it is easier to identify them for particular values of the order n and size m because we have narrowed down the possible extremal graphs. We indicate that some of our ideas extend to other degree-based topological indices as well.

Abstract. Given a bipartite graph [Formula: see text] in which any vertex in [Formula: see text] (resp., [Formula: see text]) has degree at most [Formula: see text] (resp., [Formula: see text]), suppose there is a partition of [Formula: see text] that is a refinement of the bipartition [Formula: see text] such that the parts in [Formula: see text] (resp., [Formula: see text]) have size at least [Formula: see text] (resp., [Formula: see text]). We prove that the condition [Formula: see text] is sufficient for the existence of an independent set of vertices of [Formula: see text] that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos.

We wish to bring attention to a natural but slightly hidden problem, posed by Erdös and Nešetřil in the late 1980s, an edge version of the degree--diameter problem. Our main result is that, for any graph of maximum degree $\Delta$ with more than $1.5 \Delta^t$ edges, its line graph must have diameter larger than $t$. In the case where the graph contains no cycle of length $2t+1$, we can improve the bound on the number of edges to one that is exact for $t\in\{1,2,3,4,6\}$. In the case $\Delta=3$ and $t=3$, we obtain an exact bound. Our results also have implications for the related problem of bounding the distance-$t$ chromatic index, $t>2$; in particular, for this, we obtain an upper bound of $1.941\Delta^t$ for graphs of large enough maximum degree $\Delta$, markedly improving on earlier bounds for this parameter.