Search

AbstractThe degree/diameter problemasks: Given natural numbers dand kwhat is the order (that is, the maximum number of vertices) nd,kthat can be contained in a graph of maximum degree dand diameter at most k? The degree/diameter problem is wide open for most values of dand k.A general upper bound exists; it is called the Moore bound.Graphs whose order attains the Moore boundare called Moore graphs.Since the degree/diameter problem is considered to be very difficult in general, it is worthwhile to consider it for special classes of graphs. In this paper we consider the degree/diameter problem on trees, special types of trees such as Cayley trees, caterpillars, lobsters, banana trees and firecracker trees, as well as for tree-like structures such as pseudotrees. We obtain new nd,kvalues and provide corresponding constructions.

AbstractHartsfeld and Ringel in 1990 introduced the concept of an antimagic labelingof a graph, that is, a vertex antimagic edge labelingand they also conjectured that every connected graph, except K2, is antimagic. As a means of providing an incremental advance towards proving the conjecture of Hartsfield and Ringel, in this paper we provide constructions whereby, given any degree sequence pertaining to a tree, we can construct two different vertex antimagic edge trees with the given degree sequence. Moreover, we modify a construction presented for trees to obtain an antimagic unicyclic graph with a given degree sequence pertaining to a unicyclic graph.

We examine the existing constructions of the smallest known vertex‐transitive graphs of a given degree and girth 6. It turns out that most of these graphs can be described in terms of regular lifts of suitable quotient graphs. A further outcome of our analysis is a precise identification of which of these graphs are Cayley. We also investigate higher level of transitivity of the smallest known vertex‐transitive graphs of a given degree and girth 6 and relate their constructions to near‐difference sets. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:265‐284, 2011

AbstractAn antimagic labelingof a graph with qedges is a bijection from the set of edges to the set of integers {1, 2, …, q} such that all vertex weights are pairwise distinct, where the vertex weightis the sum of labels of all edges incident with the vertex.Let [n] = {1, 2, … n}. A completely separating systemon [n] is a collection Cof subsets of [n] in which, for each pair a≠ b∊ [n], there exist A, B∊ Csuch that a∊ A, b∉ Aand b∊ B, a∉ B.Recently, a relationship between completely separating systems and labeling of graphs has been shown to exist. Based on this relationship, antimagic labelings of various graphs have been constructed. In this paper, we extend our method to produce more general results for generalized web graphs.

AbstractUsing eigenvalue analysis, it was shown by Erdös et al.that with the exception of C4, there are no graphs of diameter 2, maximum degree dand d2vertices. In this paper, we prove a number of structural properties of regular graphs of diameter 2, maximum degree dand order d2- 1.

AbstractIn this note we present some of the open problems on various aspects of graph labelings which were posed by the participants during IWOGL 2009 and which have not been included in any of the other papers appearing in this volume.

AbstractFor a graph G, let σ(G) and δ(G) denote, respectively, its sum number and minimum degree. Trivially, σ(G) ≥ δ(G). A nontrivial connected graph Gis called a k -optimum summable graph, where k≥ 1, if σ(G) = δ(G) = k. In this paper, we show that if Gis a k-optimum summable graph of order n, k≥ 3, then (1) n≥2k; (2) the complete bipartite graph Kk,n-kis not a spanning subgraph of G. We also describe new families of k-optimum summable graphs for k≥ 1.

It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 112–126, 2005