On k -diameter of k -connected graphs

Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d _k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d _k (G). For a fixed positive integer d, some conditions to insure d _k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d _k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).     

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.     

k-Subdomination in graphs

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑_uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ_ks(G), is the minimum of ∑_vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ_ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ_ks(G), the signed domination number γ_s(G) and the majority domination number γ_maj(G).     

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.     

Efficient algorithms for a constrained k-tree core problem in a tree network

Let T=(V,E) be a free tree in which each vertex has a weight and each edge has a length. Let n=|V|. Given T and parameters k and l, a (k,l)-tree core is a subtree X of T with diameter l, having k leaves, which minimizes the sum of the weighted distances from all vertices in T to X. In this paper, two efficient algorithms are presented for finding a (k,l)-tree core of T. The first algorithm has O(n²) time complexity for the case that each edge has an arbitrary length. The second algorithm has O(lkn) time complexity for the case that the lengths of all edges are 1. The (k,l)-tree core problem has an application in distributed database systems.     

(k,+)-distance-hereditary graphs

In this work we introduce, characterize, and provide algorithmic results for (k,+)-distance-hereditary graphs, k0. These graphs can be used to model interconnection networks with desirable connectivity properties; a network modeled as a (k,+)-distance-hereditary graph can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is bounded by the distance in the non-faulty graph plus an integer constant k. The class of all these graphs is denoted by DH(k,+). By varying the parameter k, classes DH(k,+) include all graphs and form a hierarchy that represents a parametric extension of the well-known class of distance-hereditary graphs.     

k-Lucas numbers and associated bipartite graphs

For a positive integer k2, the k-Fibonacci sequence {g_n^(k)} is defined as: g₁^(k)==g_k−2^(k)=0, g_k−1^(k)=g_k^(k)=1 and for n>k2, g_n^(k)=g_n−1^(k)+g_n−2^(k)++g_n−k^(k). Moreover, the k-Lucas sequence {l_n^(k)} is defined as l_n^(k)=g_n−1^(k)+g_n+k−1^(k) for n1. In this paper, we consider the relationship between g_n^(k) and l_n^(k) and 1-factors of a bipartite graph.     

On the structure of extremal graphs of high girth

Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present several results where this question is answered affirmatively. For example, this is always the case for (i) v ≥ 8 and n = 5, or (ii) when v is large compared to n: v ≥ , where a = n - 3 - , n ≥ 12. On the other hand we prove that the answer to the question is negative for v = 2n + 2 ≥ 26. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 147–153, 1997     

On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

Randomized k-server algorithms for growth-rate bounded graphs

The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. While the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k)-competitive ratios. Prior to this work only few specific cases of this problem were solved. For arbitrary metric spaces, this goal may be approached by using probabilistic metric approximation techniques. This paper gives the first results in this direction, obtaining o(k)-competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k.     

On k-graceful,locally finite graphs

While a finite, bipartite graph G can be k-graceful for every k ≥ 1, a finite nonbipartite G can be k-graceful for only finitely many values of k. An improved bound on such possible values of k is presented. Definitions are extended to infinite graphs, and it is shown that if G is locally finite and vertex set V(G) and edge set E(G) are countably infinite, then for each k ≥ 1 the graph G has a k-graceful numbering h mapping V(G) onto the set of nonnegative integers.     

On extremal unicyclic molecular graphs with maximal Hosoya index

Let G be a unicyclic n-vertex graph and Z(G) be its Hosoya index, let F_n stand for the nth Fibonacci number. It is proved in this paper that Z(G)≤F_n+1+F_n−1 with the equality holding if and only if G is isomorphic to C_n, the n-vertex cycle, and that if G≠C_n then Z(G)≤F_n+1+2F_n−3 with the equality holding if and only if G=Q_n or D_n, where graph Q_n is obtained by pasting one endpoint of a 3-vertex path to a vertex of C_n−2 and D_n is obtained by pasting one endpoint of an (n−3)-vertex path to a vertex of C₄.     

Pancyclicity mod k of claw-free graphs and K1,4-free graphs

For any natural number k, a graph G is said to be pancyclic mod k if it contains a cycle of every length modulo k. In this paper, we show that every K_1,4-free graph G with minimum degree δ(G)k+3 is pancyclic mod k and every claw-free graph G with δ(G)k+1 is pancyclic mod k, which confirms Thomassen's conjecture (J. Graph Theory 7 (1983) 261–271) for claw-free graphs.     

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.