✦ LIBER ✦

On diameter of permutation graphs

✍ Scribed by Gu, Weizhen

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 109 KB
Volume: 33
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199905)33:3<161::aid-net1>3.0.co;2-3

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a connected graph with n vertices. Let a be a permutation in S n . The a-generalized graph over G, denoted by P a (G), consists of two disjoint, identical copies of G along with edges £a(£). In this paper, we investigated the relation between diameter of P a (G) and diameter of G for any permutation

📜 SIMILAR VOLUMES

Decreasing the diameter of bounded degre

Decreasing the diameter of bounded degree graphs

✍ Noga Alon; András Gyárfás; Miklós Ruszinkó 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

Diameters of finite upper half plane gra

Diameters of finite upper half plane graphs

✍ Angel, Jeff; Evans, Ronald 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 370 KB 👁 1 views

Let GF(q) be a finite field of q elements. Let G denote the group of matrices M ( z , y) = (," y ) over GF(q) with y # 0. Fix an irreducible polynomial For each a E G F ( q ) , let X , be the graph whose vertices are the q2 -q elements of G, with two vertices M ( z , y), M ( v , w) joined by an edg

On the superconnectivity and the conditi

On the superconnectivity and the conditional diameter of graphs and digraphs

✍ Carmona, A.; F�brega, J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

It has been proved that if the diameter D of a digraph G satisfies D Յ 2ᐉ Ϫ 2, where ᐉ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D Յ 2ᐉ Ϫ 1, then G is edge-superconnected. In this paper, we studied some similar condi

The number of labeled graphs placeable b

The number of labeled graphs placeable by a given permutation

✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 370 KB 👁 2 views

Let S be a finite set and u a permutation on S. The permutation u\* on the set of 2-subsets of S is naturally induced by u. Suppose G is a graph and V(G), €(G) are the vertex set, the edge set, respectively. Let V(G) = S. If €(G) and u\*(€(G)), the image of €(G) by u\*, have no common element, then

Pebbling in diameter two graphs and prod

Pebbling in diameter two graphs and products of paths

✍ Clarke, T. A.; Hochberg, R. A.; Hurlbert, G. H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB 👁 1 views

Results regarding the pebbling number of various graphs are presented. We say a graph is of Class 0 if its pebbling number equals the number of its vertices. For diameter d we conjecture that every graph of sufficient connectivity is of Class 0. We verify the conjecture for d = 2 by characterizing t

Antipodal distance-regular graphs of dia

Antipodal distance-regular graphs of diameter four and five

✍ Tilla Schade 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 179 KB 👁 2 views

An antipodal distance-regular graph of diameter four or five is a covering graph of a connected strongly regular graph. We give existence conditions for these graphs and show for some types of strongly regular graphs that no nontrivial covers exist.