✦ LIBER ✦

A generalization of hypercubes: Complemented graphs

✍ Scribed by J. Nieminen; M. Peltola

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 486 KB
Volume: 12
Category: Article
ISSN: 0893-9659
DOI: 10.1016/s0893-9659(99)00040-3

No coin nor oath required. For personal study only.

✦ Synopsis

Communicated by A. Tucker

Abstract--Complemented graphs are a direct generalization of hypercubes as well as a special class of prime convex intersection graphs. The n-tuple representation of points of a hypercube Qn is extended to prime convex intersection graphs.

📜 SIMILAR VOLUMES

Combinatorial properties of generalized

Combinatorial properties of generalized hypercube graphs

✍ Dyi-Rong Duh; Gen-Huey Chen; D.Frank Hsu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 406 KB

Generalized hypercubes and (0,2)-graphs

✍ Jean Marie Laborde; RafaïMourad Madani 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 842 KB

A generalized hypercube Qd(S) (S s { 1,2, . , d}) has {0, l}d as vertex set and two vertices are joined whenever their mutual distance in Qd belongs to S. These graphs have been introduced in (Berrachedi and Mollard, 1996) where the notion mainly investigated there is graph embedding, especially, in

A generalization of chordal graphs

✍ P. D. Seymour; R. W. Weaver 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 487 KB

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In t

A generalization of outerplanar graphs

✍ L. Oubiña; R. Zucchello 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 898 KB

l[Rt G be a planar graph and W a set of vertices, G is W-outerplanar if it can be embedded in the plane so that all vertices of W lie on the exterior face. We give a characterization of these graphs by forbidden subgraphs, an upper bound on the number of edges, and other properties which lead to an

A generalization of perfect graphs?i-per

A generalization of perfect graphs?i-perfect graphs

✍ Cai, Leizhen; Corneil, Derek 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 1003 KB

Let i be a positive integer. We generalize the chromatic number x ( G ) of G and the clique number w(G) of G as follows: The i-chromatic number of G , denoted by x Z ( G ) , is the least number k for which G has a vertex partition V,, V,, . . . , Vk: such that the clique number of the subgraph induc

Partial Complement of a Graph

✍ H.B. Walikar 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 172 KB