✦ LIBER ✦

Every connected graph is a query graph

✍ Scribed by Peter M. Winkler

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 173 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110213

No coin nor oath required. For personal study only.

✦ Synopsis

Let Vbe a set of bit strings of length k, i.e., V C {0, l}'. The query graph Q ( V ) is defined as follows: the vertices of Q(V) are the elements of V, and {O,V} is an edge of Q ( V ) if and only if no other W E Vagrees with U in all the positions in which V does. If Vrepresents the set of keys for a statistical data base in which queries that match only one key are rejected, then the security of the individual data is related to the graph Q(V).

Ernst L e i s showed that graphs belonging to any of several classes could be represented as query graphs and asked whether any connected graph could be so represented. We answer his question in the affirmative by making use of a spanning tree with special properties.

📜 SIMILAR VOLUMES

Every connected, locally connected graph

Every connected, locally connected graph is upper embeddable

✍ Ladislav Nebeský 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract In this Note it is proved that every connected, locally connected graph is upper embeddable. Moreover, a lower bound for the maximum genus of the square of a connected graph is given.

Every 3-connected, locally connected, cl

Every 3-connected, locally connected, claw-free graph is Hamilton-connected

✍ Asratian, A. S. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 639 KB

A graph G is locally connected if the subgraph induced by the neighbourhood of each vertex is connected. We prove that a locally connected graph G of orderp 2 4, containing no induced subgraph isomorphic to K1,31 is Hamilton-connected if and only if G is 3connected.

Every connected, locally connected nontr

Every connected, locally connected nontrivial graph with no induced claw is hamiltonian

✍ David J. Oberly; Slobodan K. Simić; David P. Sumner 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB

## Abstract A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on __p__ ≥ 3 vertices and having no induced __K__~1,3~ is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtain

Every 3-connected claw-free Z8-free grap

Every 3-connected claw-free Z8-free graph is Hamiltonian

✍ Hong-Jian Lai; Liming Xiong; Huiya Yan; Jin Yan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

## Abstract In this article, we first show that every 3‐edge‐connected graph with circumference at most 8 is supereulerian, which is then applied to show that a 3‐connected claw‐free graph without __Z__~8~ as an induced subgraph is Hamiltonian, where __Z__~8~ denotes the graph derived from identify

Every Graph Is an Integral Distance Grap

Every Graph Is an Integral Distance Graph in the Plane

✍ Hiroshi Maehara; Katsuhiro Ota; Norihide Tokushige 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 290 KB

We prove that every finite simple graph can be drawn in the plane so that any two vertices have an integral distance if and only if they are adjacent. The proof is constructive.

Every Planar Graph Is 5-Choosable

✍ C. Thomassen 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 56 KB

We prove the statement of the title, which was conjectured in 1975 by V. G. Vizing and, independently, in 1979 by P. Erdös, A. L. Rubin, and H. Taylor. (i) 1994 Academic Press, Inc.