Premium
Every connected graph is a query graph
Author(s) -
Winkler Peter M.
Publication year - 1987
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190110213
Subject(s) - combinatorics , mathematics , graph , complement graph , line graph , discrete mathematics , voltage graph
Let V be a set of bit strings of length k , i.e., V ⊂ {0, 1} k . The query graph Q(V) is defined as follows: the vertices of Q(V) are the elements of V , and { ū, v̄ } is an edge of Q(V) if and only if no other w̄ ϵ V agrees with ū in all the positions in which v̄ does. If V represents 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 Leiss 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.