✦ LIBER ✦

Maximum genus and maximum nonseparating independent set of a 3-regular graph

✍ Scribed by Yuangqiu Huang; Yanpei Liu

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 440 KB
Volume: 176
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00299-3

No coin nor oath required. For personal study only.

✦ Synopsis

A set J C V is called a nonseparating independent set (nsis) of a connected graph G = (V, E), if J is an independent set of G, i.e., E A {uv [ Vu, v E J} = 0, and G -J is connected. We call z(G) = maxJ{lJ[ tJ is an nsis of G} the nsis number of G. Let G be a 3-regular connected graph; we prove that the maximum genus, denoted by 7M(G), of G is equal to z(G). Then, according to this result, some new characterizations of the maximum genus 7M(G) are obtained.

📜 SIMILAR VOLUMES

Algorithms for a maximum clique and a ma

Algorithms for a maximum clique and a maximum independent set of a circle graph

✍ F. Gavril 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 523 KB

## Abstract Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum indepen

Generation of maximum independent sets o

Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph

✍ Toshinobu Kashiwabara; Sumio Masuda; Kazuo Nakajima; Toshio Fujisawa 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 760 KB

Maximum independent sets of circular-arc

Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs

✍ Zheng, S. Q. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 421 KB 👁 2 views

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G , our algorithm computes a maximum independent set of G in O ( n ) space and O ( n ) or O(n log n ) time, depending on whether the

Graphs with unique minimum edge dominati

Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices

✍ Jerzy Topp 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 816 KB

Topp, J., Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices, Discrete Mathematics 12 1 (1993) 199-210. A set I of vertices of a graph G is an independent set if no two vertices of I are adjacent. A set M of edges of G is an edge dominating s

Face Size and the Maximum Genus of a Gra

Face Size and the Maximum Genus of a Graph 1. Simple Graphs

✍ Yuanqiu Huang; Yanpei Liu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 150 KB

This paper shows that a simple graph which can be cellularly embedded on some closed surface in such a way that the size of each face does not exceed 7 is upper embeddable. This settles one of two conjectures posed by Nedela and S8 koviera (1990, in ``Topics in Combinatorics and Graph Theory,'' pp.

Survey of results on the maximum genus o

Survey of results on the maximum genus of a graph

✍ Richard D. Ringeisen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 619 KB

## Abstract Some of the early questions concerning the maximum genus of a graph have now been answered. In this paper we survey the progress made on such problems and present some recent results, outlining proofs for some of the major theorems.