An extremal bandwidth problem for bipartite graphs

This paper discusses the problem of finding the maximum number of edges E(m, n, B) in a bipartite graph having partite set sizes m and n and bandwidth B. Exact values for E(m, n, B) are found for many cases. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 278–289, 2000     

The extremal function for 3-linked graphs

A graph is k-linked if for every set of 2k distinct vertices {s₁,…,s_k,t₁,…,t_k} there exist disjoint paths P₁,…,P_k such that the endpoints of P_i are s_i and t_i. We prove every 6-connected graph on n vertices with 5n−14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on n vertices with 5n−15 edges that are not 3-linked for arbitrarily large values of n.     

Variable neighborhood search for extremal graphs 3

In the set of bicolored trees with given numbers of black and of white vertices we describe those for which the largest eigenvalue is extremal (maximal or minimal). The results are first obtained by the automated system AutoGraphiX, developed in GERAD (Montreal), and verified afterwards by theoretical means.     

Variable neighborhood search for extremal graphs 3

In the set of bicolored trees with given numbers of black and of white vertices we describe those for which the largest eigenvalue is extremal (maximal or minimal). The results are first obtained by the automated system AutoGraphiX, developed in GERAD (Montreal), and verified afterwards by theoretical means.     

On extremal problems of graphs and generalized graphs

Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n ₀ everyr-graph ofn vertices andn ^{r−ε(l, r)} r-tuples containsr. l verticesx ^(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples occur in ther-graph.     

Maximal and extremal singular graphs

A graph G is singular if the nullspace of its adjacency matrix is nontrivial. Such a graph contains induced subgraphs called singular configurations of nullity 1. We present two algorithms. One is for the construction of a maximal singular nontrivial graph G containing an induced subgraph, which is a singular configuration with the support of a vector in its nullspace as in that of G. The second is for the construction of a nut graph, a graph of nullity one whose null vector has no zero entries. An extremal singular graph of a given order, with the maximal nullity and support, has a nut graph as a maximal singular configuration.     

An extremal problem for edge domination insensitive graphs

A connected graph is edge domination insensitive if the domination number is unchanged when any single edge is removed. The minimum number of edges required by such a graph is determined. Similar results are given when the graph must remain connected upon any edge's removal and when the dominating set must remain fixed.     

Minimizer graphs for a class of extremal problems

We consider the family of graphs with a fixed number of vertices and edges. Among all these graphs, we are looking for those minimizing the sum of the square roots of the vertex degrees. We prove that there is a unique such graph, which consists of the largest possible complete subgraph plus only one other non‐isolated vertex. The same result is proven for any power of the vertex‐degrees less than one half. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 230–240, 2002; DOI 10.1002/jgt.10025     

An extremal problem for paths in bipartite graphs

A formula is found for the maximum number of edges in a graph G ? K(a, b) which contains no path P_2l for l > c. A similar formula is found for the maximum number of edges in G ? K(a, b) containing no P_{2l + 1} for l > c. In addition, all extremal graphs are determined.     

An extremal problem for cycles in hamiltonian graphs

For integersp andr with 3 r p – 1, letf(p, r) denote the maximum number of edges in a hamiltonian graph of orderp which does not contain a cycle of lengthr. Results from literature on the determination off(p, r) are collected and a number of new lower bounds, many of which are conjectured to be best possible, are given. The main result presented is the proof thatf(p, 5) = (p – 3)²/4 + 5 for oddp 11.George Hendry died during the publication process.Supported by Deutsche Forschungsgemeinschaft (DFG), Grant We 1265.     

An extremal problem in geodetic graphs

An upper bound for the number of lines in a geodetic block of diameter d on p points is obtained, using some new general properties of geodetic blocks which are also of independent interest.     

Unicyclic graphs with extremal Lanzhou index

Very recently D.Vuki?evi? et al.[8] introduced a new topological index for a molecular graph G named Lanzhou index as ■,where d_u and ■ denote the degree of vertex u in G and in its complement respectively.Lanzhou index Lz(G) can be expressed as(n-1)M₁(G)-F(G),where M₁(G) and F(G) denote the first Zagreb index and the forgotten index of G respectively,and n is the number of vertices in G.It turns out that Lanzhou index outperforms M₁(G) and F(G) in pred...     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

On some extremal connectivity results for graphs and matroids

Dirac and Halin have shown for n = 2 and n = 3 respectively that a minimally n-connected graph G has at least ((n–1)|V(G)|–2n)/(2n–1) vertices of degree n. This paper determines the graphs which are extremal with respect to these two results and, in addition, establishes a similar extremal result for minimally connected matroids.