✦ LIBER ✦

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

✍ Scribed by Kiyoshi Ando

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 275 KB
Volume: 135
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)e0093-j

No coin nor oath required. For personal study only.

✦ Synopsis

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 minimum cut of G (resp. G) contains all the elemental fragments of c (resp. G), then Moreover, for any given positive integers k and k, there is a critically (k, k)-connected graph for which the above equality holds.

📜 SIMILAR VOLUMES

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

An upper bound for the radius of a 3-con

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

✍ Jochen Harant 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 286 KB

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

An upper bound for total colouring of gr

An upper bound for total colouring of graphs

✍ Colin J.H. McDiarmid; Abdón Sánchez-Arroyo 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 235 KB

An upper bound for total colouring of graphs, Discrete Mathematics 111 (1993) 3899392. We give an upper bound on the number of colours required to extend a given vertex colouring of a graph to a total colouring. This shows that for any simple graph there is a total colouring using at most :d + 3 co

An upper bound for the ramsey number r(K

An upper bound for the ramsey number r(K5 − e)

✍ H. Harborth; I. Mengersen 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB 👁 1 views

An upper bound for the Ramsey numbers r(

An upper bound for the Ramsey numbers r(K3,G)

✍ Wayne Goddard; Daniel J. Kleitman 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 372 KB

The Ramsey number r(H, G) is defined as the minimum N such that for any coloring of the edges of the N-vertex complete graph KN in red and blue, it must contain either a ted H or a blue G. In this paper we show that for any graph G without isolated vertices, r(K,, G)< 2qf 1 where G has q edges. In o

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