A Cauchy-Davenport type result for arbitrary regular graphs.
A characterization of diameter-2-critical graphs with no antihole of length four
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence...
A characterization of the interval function of a connected graph
A characterization of the interval function of a (finite or infinite) connected graph
By the interval function of a finite connected graph we mean the interval function in the sense of H. M. Mulder. This function is very important for studying properties of a finite connected graph which depend on the distance between vertices. The interval function of a finite connected graph was characterized by the present author. The interval function of an infinite connected graph can be defined similarly to that of a finite one. In the present paper we give a characterization of the interval...
A characterization of the set of all shortest paths in a connected graph
Let be a (finite undirected) connected graph (with no loop or multiple edge). The set of all shortest paths in is defined as the set of all paths , then the lenght of does not exceed the length of . While the definition of is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of : a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...
A conjecture of Biggs concerning the resistance of a distance-regular graph.
A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles
For any we construct graphs of degree , diameter , and order , obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of has been known [3] but it applies only to special values of degrees depending on prime powers.
A family of nonregular distance monotone graphs
A generalization of branch weight centroids
A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs
ACM Computing Classification System (1998): G.2.2.We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes...
A maximum degree theorem for diameter-2-critical graphs
A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a...
A metric on a system of ordered sets
In [3] a metric on a system of isomorphism classes of ordered sets was defined. In this paper we define another metric on the same system and investigate some of its properties. Our approach is motivated by a problem from practice.
A modification of the median of a tree
The concept of median of a tree is modified, considering only distances from the terminal vertices instead of distances from all vertices.
A Moore-like bound for graphs of diameter 2 and given degree, obtained as abelian lifts of dipoles.
A New Method for Computing the Eccentric Connectivity Index of Fullerenes
ACM Computing Classification System (1998): G.2.2, G.2.3.The eccentric connectivity index of the molecular graph G, ξ^c (G), was proposed by Sharma, Goswami and Madan. It is defined as ξ^c (G) = Σu∈V(G)degG(u) ecc(u), where degG(x) denotes the degree of the vertex x in G and ecc(u) = Max{d(x, u) | x ∈ V (G)}. In this paper this graph invariant is computed for an infinite class of fullerenes by means of group action.
A new proof of a characterization of the set of all geodesics in a connected graph
A New Proof of the Szeged-Wiener Theorem
A note on commuting graphs for symmetric groups.
A note on degree-continuous graphs
The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.
A note on -free precolouring with colours.