𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterization of the graphs with boxicity ⩽2

✍ Scribed by Martin Quest; Gerd Wegner

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
360 KB
Volume
81
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The intersection graph of a family 8TI of sets has the sets in %' as vertices and an edge between two sets iff they have nonempty intersection. Following Roberts [4] the boxicity b(G) of a graph G is defined as the smallest d such that G is the intersection graph of boxes in Euclidean d-space, i.e. parallelepipeds with edges parallel to the coordinate axes. In this paper we will give a combinatorial characterization of the graphs with b(G)s2, called boxicity 2-graphs, by means of the arrangement of zeros and ones in special matrices attached to the graph.

📜 SIMILAR VOLUMES

Characterization of graphs with hall num
Characterization of graphs with hall number 2
✍ Changiz Eslahchi; Matthew Johnson 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB

## Abstract Hall's condition is a simple requirement that a graph __G__ and list assignment __L__ must satisfy if __G__ is to have a proper __L__‐colouring. The Hall number of __G__ is the smallest integer __m__ such that whenever the lists on the vertices each has size at least __m__ and Hall's co

On the parameter v2(h)⩽6h for L2-coloure
On the parameter v2(h)⩽6h for L2-coloured graphs
✍ Mario Gionfriddo; Salvatore Milici 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 346 KB

We prove that or,@) s 6k, for L~-coioured graphs. Let G = (V, S) be an undirected graph. For every pair of distinct elements X, y E V, the &stcPnce d(x, y) is the length of a shortest path joining them if one exists, otherwise d(x, y) = 00. In the case x = y, it is d(x, y) = 0. If 6; = (V, S) is a

A characterization of graphs G with G ≈
A characterization of graphs G with G ≈ K2(G)
✍ Chai-Ling Deng; Chong-Keang Lim 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 311 KB

A graph G is called a D-graph if for every set of cliques of G whose pairwise intersections are nonempty there is a vertex of G common to all the cliques of the set. A D-graph G is called a Dl-graph if it has the T 1 property: for any two distinct vertices x and y of G, there exist cliques C and D o

Characterization of maximum critically 2
Characterization of maximum critically 2-connected graphs
✍ R. C. Entringer 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

## Abstract A graph __G__ is critically 2‐connected if __G__ is 2‐connected but, for any point __p__ of __G, G — p__ is not 2‐connected. Critically 2‐connected graphs on __n__ points that have the maximum number of lines are characterized and shown to be unique for __n__ ⩾ 3, __n__ ≠ 11.

Characterizations of 2-variegated graphs
Characterizations of 2-variegated graphs and of 3-variegated graphs
✍ Vasanti N. Bhat-Nayak; S.A. Choudum; Ranjan N. Naik 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 586 KB

A graph is said to be k-variegated if its vertex set can be partiticned into k equal parts such that each vertex is adjacent to exactly one vertex from every othe,r part not co;ltaininT, it. We prove that a graph G on 2n vertices is 2-variegated if and only if there exists a bet S of n independent e