✦ LIBER ✦

Genus characterizes the complexity of certain graph problems: Some tight results

✍ Scribed by Jianer Chen; Iyad A. Kanj; Ljubomir Perković; Eric Sedgwick; Ge Xia

Book ID: 108166525
Publisher: Elsevier Science
Year: 2007
Tongue: English
Weight: 213 KB
Volume: 73
Category: Article
ISSN: 0022-0000
DOI: 10.1016/j.jcss.2006.11.001

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The complexity of some graph colouring p

The complexity of some graph colouring problems

✍ Keith Edwards 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 896 KB

On the complexity of some problems relat

On the complexity of some problems related to graph extensions

✍ M. B. Abrosimov 📂 Article 📅 2010 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 510 KB

On the complexity of some edge-partition

On the complexity of some edge-partition problems for graphs

✍ Zbigniew Lonc 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 515 KB

Some results on characterizing the edges

Some results on characterizing the edges of connected graphs with a given domination number

✍ Laura A. Sanchis 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 821 KB

A dominatin# set for a graph G = (V, E) is a subset of vertices V' c\_ V such that for all v • V-V' there exists some u• V' for which {v,u} •E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let mz(G, D) denote the nu