The homomorphism domination exponent
Publication
, Journal Article
Kopparty, S; Rossman, B
Published in: European Journal of Combinatorics
October 1, 2011
We initiate a study of the homomorphism domination exponent of a pair of graphs F and G, defined as the maximum real number c such that |Hom(F,T)|≥|Hom(G,T)|c for every graph T. The problem of determining whether HDE(F,G)≥1 is known as the homomorphism domination problem, and its decidability is an important open question arising in the theory of relational databases. We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of graphs F and G for which HDE(F,G) is computable. In particular, we present a linear program computing HDE(F,G) in the special case, where F is chordal and G is series-parallel. © 2011 Elsevier Ltd.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
European Journal of Combinatorics
DOI
ISSN
0195-6698
Publication Date
October 1, 2011
Volume
32
Issue
7
Start / End Page
1097 / 1114
Related Subject Headings
- Computation Theory & Mathematics
- 4904 Pure mathematics
- 0101 Pure Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Kopparty, S., & Rossman, B. (2011). The homomorphism domination exponent. European Journal of Combinatorics, 32(7), 1097–1114. https://doi.org/10.1016/j.ejc.2011.03.009
Kopparty, S., and B. Rossman. “The homomorphism domination exponent.” European Journal of Combinatorics 32, no. 7 (October 1, 2011): 1097–1114. https://doi.org/10.1016/j.ejc.2011.03.009.
Kopparty S, Rossman B. The homomorphism domination exponent. European Journal of Combinatorics. 2011 Oct 1;32(7):1097–114.
Kopparty, S., and B. Rossman. “The homomorphism domination exponent.” European Journal of Combinatorics, vol. 32, no. 7, Oct. 2011, pp. 1097–114. Scopus, doi:10.1016/j.ejc.2011.03.009.
Kopparty S, Rossman B. The homomorphism domination exponent. European Journal of Combinatorics. 2011 Oct 1;32(7):1097–1114.
Published In
European Journal of Combinatorics
DOI
ISSN
0195-6698
Publication Date
October 1, 2011
Volume
32
Issue
7
Start / End Page
1097 / 1114
Related Subject Headings
- Computation Theory & Mathematics
- 4904 Pure mathematics
- 0101 Pure Mathematics