Page 1 Next

Displaying 1 – 20 of 43

Showing per page

A characterization of diameter-2-critical graphs with no antihole of length four

Teresa Haynes, Michael Henning (2012)

Open Mathematics

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 (finite or infinite) connected graph

Ladislav Nebeský (2001)

Czechoslovak Mathematical Journal

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

Ladislav Nebeský (1994)

Mathematica Bohemica

Let G be a (finite undirected) connected graph (with no loop or multiple edge). The set of all shortest paths in G 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 construction of large graphs of diameter two and given degree from Abelian lifts of dipoles

Dávid Mesežnikov (2012)

Kybernetika

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

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Markov, Minko, Ionut Andreica, Mugurel, Manev, Krassimir, Tapus, Nicolae (2012)

Serdica Journal of Computing

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

Teresa Haynes, Michael Henning, Lucas Merwe, Anders Yeo (2014)

Open Mathematics

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

Alfonz Haviar, Pavel Klenovčan (1996)

Mathematica Bohemica

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

Bohdan Zelinka (1993)

Mathematica Bohemica

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

A New Method for Computing the Eccentric Connectivity Index of Fullerenes

Ghorbani, Modjtaba, Malekjani, Khadijeh (2012)

Serdica Journal of Computing

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 note on degree-continuous graphs

Chiang Lin, Wei-Bo Ou (2007)

Czechoslovak Mathematical Journal

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.

Currently displaying 1 – 20 of 43

Page 1 Next