✦ LIBER ✦

An upper bound for the radius of a 3-connected graph

✍ Scribed by Jochen Harant

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 286 KB
Volume: 122
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90306-e

No coin nor oath required. For personal study only.

✦ Synopsis

For a 3-connected graph with radius r containing n vertices, in [1] r < n/4 + O(log n) was proved and r < n/4 + const was conjectured.

Here we prove r < n/4 + 8.

Let G be a simple 3-connected finite graph on n vertices with vertex set V(G) and edge set E(G). For X, YE V(G) we denote by d(X, Y) the distance between X and Y. A vertex ZE V(G) is called a central vertex of G if max d(Z, Y)= min max d(X, Y).

YEV(G) XEV(G) YEV(G)

📜 SIMILAR VOLUMES

A Sharp Upper Bound of the Spectral Radi

A Sharp Upper Bound of the Spectral Radius of Graphs

✍ Yuan Hong; Jin-Long Shu; Kunfu Fang 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 88 KB

An upper bound for orders of certain (k,

An upper bound for orders of certain (k, k))-connected graphs

✍ Kiyoshi Ando 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 275 KB

A fragment of a connected graph G is a subset A of V(C) consisting of components of G-S such that V(G)-S-A #0 where S is a minimum cut of G. A graph G is said to be (k, I;)- We prove the following result. Let k and k be integers with 1 <i < k, and let G be a critically (k, k)-connected graph. If no

A general upper bound for the cyclic chr

A general upper bound for the cyclic chromatic number of 3-connected plane graphs

✍ Hikoe Enomoto; Mirko Horňák 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 457 KB 👁 1 views

## Abstract The cyclic chromatic number of a plane graph __G__ is the smallest number χ~__c__~(__G__) of colors that can be assigned to vertices of __G__ in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer an

An upper bound for the path number of a

An upper bound for the path number of a graph

✍ Alan Donald 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 529 KB

## Abstract The path number of a graph __G__, denoted __p(G)__, is the minimum number of edge‐disjoint paths covering the edges of __G.__ Lovász has proved that if __G__ has __u__ odd vertices and __g__ even vertices, then __p(G)__ ≤ 1/2 __u__ + __g__ ‐ 1 ≤ __n__ ‐ 1, where __n__ is the total numbe

An upper bound for the harmonious chroma

An upper bound for the harmonious chromatic number of a graph

✍ Sin-Min Lee; John Mitchem 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o

An upper bound for the k-domination numb

An upper bound for the k-domination number of a graph

✍ E. J. Cockayne; B. Gamble; B. Shepherd 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 2 views

The kdomination number of a graph G, y k ( G ) , is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k. then YAG) 5 kp/(k + 1).