Page 1 Next

## Displaying 1 – 20 of 317

Showing per page

Integers

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

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 connected graph

Czechoslovak Mathematical Journal

### A characterization of the interval function of a (finite or infinite) connected graph

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

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 $\xi$, then the lenght of $\xi$ does not exceed the length of $\varsigma$. 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.

The Electronic Journal of Combinatorics [electronic only]

### A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles

Kybernetika

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  but it applies only to special values of degrees $d$ depending on prime powers.

### A family of nonregular distance monotone graphs

Czechoslovak Mathematical Journal

### A generalization of branch weight centroids

Applicationes Mathematicae

### A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

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

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

Mathematica Bohemica

In  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

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 Moore-like bound for graphs of diameter 2 and given degree, obtained as abelian lifts of dipoles.

Acta Mathematica Universitatis Comenianae. New Series

### A New Method for Computing the Eccentric Connectivity Index of Fullerenes

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 new proof of a characterization of the set of all geodesics in a connected graph

Czechoslovak Mathematical Journal

### A New Proof of the Szeged-Wiener Theorem

Kragujevac Journal of Mathematics

### A note on commuting graphs for symmetric groups.

The Electronic Journal of Combinatorics [electronic only]

### A note on degree-continuous graphs

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.

### A note on ${K}_{\text{Δ}+1}^{-}$-free precolouring with $\text{Δ}$ colours.

The Electronic Journal of Combinatorics [electronic only]

Page 1 Next