### A Cauchy-Davenport type result for arbitrary regular graphs.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

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...

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...

Let $G$ be a (finite undirected) connected graph (with no loop or multiple edge). The set $\mathcal{L}$ of all shortest paths in $G$ is defined as the set of all paths $\xi $, then the lenght of $\xi $ does not exceed the length of $\varsigma $. While the definition of $\mathcal{L}$ is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of $\mathcal{L}$: a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...

For any $d\ge 11$ we construct graphs of degree $d$, diameter $2$, and order $\frac{8}{25}{d}^{2}+O\left(d\right)$, obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of $\frac{9}{25}{d}^{2}+O\left(d\right)$ has been known [3] but it applies only to special values of degrees $d$ depending on prime powers.

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 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...

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.

The concept of median of a tree is modified, considering only distances from the terminal vertices instead of distances from all vertices.

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.

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.