✦ LIBER ✦

On the separation number of a graph

✍ Scribed by Zevi Miller; Dan Pritikin

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 781 KB
Volume: 19
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230190604

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the following graph labeling problem, introduced by Leung et al. (3. Y-T. Leung, 0. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem. SIAM J. Comput. 13 (1984) 650-667). Let G be a graph of order n, and f a bijection from

the separation number of G, to be the maximum of If among all such bijections f . We first derive some basic relations between s ( G ) and other graph parameters. Using a general strategy for analyzing separation number in bipartite graphs, we obtain exact values for certain classes of forests and asymptotically optimal lower bounds for grids and hypercubes. *Partial support from the State of Ohio Research Challenge Program is gratefully acknowledged.

📜 SIMILAR VOLUMES

On the geodetic number of a graph

✍ Gary Chartrand; Frank Harary; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

On the Cop Number of a Graph

✍ A. Berarducci; B. Intrigila 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 608 KB

On the bondage number of a graph

✍ Yue-Li Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 162 KB

The bondage number b(G) of a graph G is the minimum cardinality of a set of edges of G whose removal from G makes the domination number of G increase. There are several papers discussed the upper bound of b(G). In this paper, we shall give an improved upper bound of b(G).

The vertex separation number of a graph

The vertex separation number of a graph equals its path-width

✍ Nancy G. Kinnersley 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 497 KB

On the Interval Number of a Triangulated

On the Interval Number of a Triangulated Graph

✍ Thomas Andreae 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB 👁 2 views

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices u and w of G are adjacent if and only if some interval for u intersect

On the interval number of a chordal grap

On the interval number of a chordal graph

✍ Edward R. Scheinerman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB 👁 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum