Document Open Access Logo

Induced Embeddings into Hamming Graphs

Authors Martin Milanic, Peter Mursic, Marcelo Mydlarz

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.28.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Martin Milanic
Peter Mursic
Marcelo Mydlarz

Cite As Get BibTex

Martin Milanic, Peter Mursic, and Marcelo Mydlarz. Induced Embeddings into Hamming Graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.28

Abstract

Let d be a positive integer. Can a given graph G be realized in R^d so that vertices are mapped to distinct points, two vertices being adjacent if and only if the corresponding points lie on a common line that is parallel to some axis? Graphs admitting such realizations have been studied in the literature for decades under different names. Peterson asked in [Discrete Appl. Math., 2003] about the complexity of the recognition problem. While the two-dimensional case corresponds to the class of line graphs of bipartite graphs and is well-understood, the complexity question has remained open for all higher dimensions.

In this paper, we answer this question. We establish the NP-completeness of the recognition problem for any fixed dimension, even in the class of bipartite graphs. To do this, we strengthen a characterization of induced subgraphs of 3-dimensional Hamming graphs due to Klavžar and Peterin. We complement the hardness result by showing that for some important classes of perfect graphs –including chordal graphs and distance-hereditary graphs– the minimum dimension of the Euclidean space in which the graph can be realized, or the impossibility of doing so, can be determined in linear time.

Subject Classification

Keywords
  • gridline graph
  • Hamming graph
  • induced embedding
  • NP-completeness
  • chordal graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Martin Aigner. The uniqueness of the cubic lattice graph. J. Combinatorial Theory, 6:282-297, 1969. Google Scholar
  2. Lowell W. Beineke, Izak Broere, and Michael A. Henning. Queens graphs. Discrete Math., 206(1-3):63-75, 1999. Google Scholar
  3. Jean-Claude Bermond, Marie-Claude Heydemann, and Dominique Sotteau. Line graphs of hypergraphs. I. Discrete Math., 18(3):235-241, 1977. Google Scholar
  4. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. Google Scholar
  5. Andreas Brandstädt, Van Bang Le, and Thomas Szymczak. Duchet-type theorems for powers of HHD-free graphs. Discrete Math., 177(1-3):9-16, 1997. Google Scholar
  6. Hajo J. Broersma, Elias Dahlhaus, and Ton Kloks. Algorithms for the treewidth and minimum fill-in of HHD-free graphs. In Graph-theoretic concepts in computer science (Berlin, 1997), volume 1335 of Lecture Notes in Comput. Sci., pages 109-117. Springer, Berlin, 1997. Google Scholar
  7. Gustav Burosch and Pier Vittorio Ceccherini. On the Cartesian dimensions of graphs. J. Combin. Inform. System Sci., 19(1-2):35-45, 1994. International Conference on Graphs and Hypergraphs (Varenna, 1991). Google Scholar
  8. L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad, and Roohani Sharma. Product dimension of forests and bounded treewidth graphs. Electron. J. Combin., 20(3):Paper 42, 14, 2013. Google Scholar
  9. Gary Theodore Chartrand. GRAPHS AND THEIR ASSOCIATED LINE-GRAPHS. ProQuest LLC, Ann Arbor, MI, 1964. Thesis (Ph.D.)-Michigan State University. Google Scholar
  10. Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Ann. of Math. (2), 164(1):51-229, 2006. Google Scholar
  11. Curtis R. Cook. Further characterizations of cubic lattice graphs. Discrete Math., 4:129-138, 1973. Google Scholar
  12. Curtis R. Cook. A note on the exceptional graph of the cubic lattice graph characterization. J. Combinatorial Theory Ser. B, 14:132-136, 1973. Google Scholar
  13. Curtis R. Cook. Representations of graphs by n-tuples. In Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), pages 303-316. Congressus Numerantium, No. X, Winnipeg, Man., 1974. Utilitas Math. Google Scholar
  14. Curtis R. Cook, B. Devadas Acharya, and V. Mishra. Adjacency graphs. In Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), pages 317-331. Congressus Numerantium, No. X. Utilitas Math., Winnipeg, Man., 1974. Google Scholar
  15. Alexander K. Dewdney. The embedding dimension of a graph. Ars Combin., 9:77-90, 1980. Google Scholar
  16. Thomas A. Dowling. Note on: "A characterization of cubic lattice graphs". J. Combinatorial Theory, 5:425-426, 1968. Google Scholar
  17. Feodor F. Dragan and Falk Nicolai. LexBFS-orderings and powers of HHD-free graphs. Int. J. Comput. Math., 71(1):35-56, 1999. Google Scholar
  18. Feodor F. Dragan, Falk Nicolai, and Andreas Brandstädt. LexBFS-orderings and powers of graphs. In Graph-theoretic concepts in computer science (Cadenabbia, 1996), volume 1197 of Lecture Notes in Comput. Sci., pages 166-180. Springer, Berlin, 1997. Google Scholar
  19. Feodor F. Dragan, Falk Nicolai, and Andreas Brandstädt. Powers of HHD-free graphs. Int. J. Comput. Math., 69(3-4):217-242, 1998. Google Scholar
  20. David Eppstein. The lattice dimension of a graph. European J. Combin., 26(5):585-592, 2005. Google Scholar
  21. Anthony B. Evans, Garth Isaak, and Darren A. Narayan. Representations of graphs modulo n. Discrete Math., 223(1-3):109-123, 2000. Google Scholar
  22. Shannon L. Fitzpatrick and Richard J. Nowakowski. The strong isometric dimension of finite reflexive graphs. Discuss. Math. Graph Theory, 20(1):23-38, 2000. Google Scholar
  23. Alan Frieze, Jon Kleinberg, R. Ravi, and Warren Debany. Line-of-sight networks. Combin. Probab. Comput., 18(1-2):145-163, 2009. Google Scholar
  24. Ronald L. Graham and Peter M. Winkler. On isometric embeddings of graphs. Trans. Amer. Math. Soc., 288(2):527-536, 1985. Google Scholar
  25. Vladimir A. Gurvich and Mikhail A. Temkin. Cellular perfect graphs. Dokl. Akad. Nauk, 326(2):227-232, 1992. Google Scholar
  26. F. Harary and C. Holzmann. Line graphs of bipartite graphs. Rev. Soc. Mat. Chile, 1:19-22, 1974. Google Scholar
  27. Frank Harary. Cubical graphs and cubical dimensions. Comput. Math. Appl., 15(4):271-275, 1988. Google Scholar
  28. Stephen T. Hedetniemi. Graphs of (0, 1)-matrices. In Recent Trends in Graph Theory (Proc. Conf., New York, 1970), pages 157-171. Lecture Notes in Mathematics, Vol. 186. Springer, Berlin, 1971. Google Scholar
  29. Marie-Claude Heydemann and Dominique Sotteau. Line-graphs of hypergraphs. II. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, volume 18 of Colloq. Math. Soc. János Bolyai, pages 567-582. North-Holland, Amsterdam-New York, 1978. Google Scholar
  30. Ian Holyer. The NP-completeness of edge-coloring. SIAM J. Comput., 10(4):718-720, 1981. Google Scholar
  31. Beverly Jamison and Stephan Olariu. On the semi-perfect elimination. Adv. in Appl. Math., 9(3):364-376, 1988. Google Scholar
  32. Janja Jerebic and Sandi Klavžar. On induced and isometric embeddings of graphs into the strong product of paths. Discrete Math., 306(13):1358-1363, 2006. Google Scholar
  33. Sandi Klavžar and Iztok Peterin. Characterizing subgraphs of Hamming graphs. J. Graph Theory, 49(4):302-312, 2005. Google Scholar
  34. Sandi Klavžar, Iztok Peterin, and Sara Sabrina Zemljič. Hamming dimension of a graph - the case of Sierpiński graphs. European J. Combin., 34(2):460-473, 2013. Google Scholar
  35. Martin Kochol. Snarks without small cycles. J. Combin. Theory Ser. B, 67(1):34-47, 1996. Google Scholar
  36. Luděk Kučera, Jaroslav Nešetřil, and Aleš Pultr. Complexity of dimension three and some related edge-covering characteristics of graphs. Theoret. Comput. Sci., 11(1):93-106, 1980. Google Scholar
  37. Renu Laskar. A characterization of cubic lattice graphs. J. Combinatorial Theory, 3:386-401, 1967. Google Scholar
  38. Van Bang Le and Nguyen Ngoc Tuy. The square of a block graph. Discrete Math., 310(4):734-741, 2010. Google Scholar
  39. László Lovász, Jaroslav Nešetřil, and Aleš Pultr. On a product dimension of graphs. J. Combin. Theory Ser. B, 29(1):47-67, 1980. Google Scholar
  40. J. Nešetřil and Aleš Pultr. A Dushnik-Miller type dimension of graphs and its complexity. In Fundamentals of computation theory (Proc. Internat. Conf., Poznań-Kórnik, 1977), pages 482-493. Lecture Notes in Comput. Sci., Vol. 56. Springer, Berlin, 1977. Google Scholar
  41. Jaroslav Nešetřil and Vojtěch Rödl. A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph. Discrete Math., 23(1):49-55, 1978. Google Scholar
  42. Stavros D. Nikolopoulos and Leonidas Palios. Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs. Discrete Math. Theor. Comput. Sci., 8(1):65-82, 2006. Google Scholar
  43. Stavros D. Nikolopoulos and Leonidas Palios. An O(nm)-time certifying algorithm for recognizing HHD-free graphs. Theoret. Comput. Sci., 452:117-131, 2012. Google Scholar
  44. Stephan Olariu. Results on perfect graphs. PhD thesis, School of Computer Science, McGill University, Montreal, 1986. Google Scholar
  45. Dale Peterson. Gridline graphs and higher dimensional extensions. Technical report, RUTCOR, Rutgers University, 1995. Google Scholar
  46. Dale Peterson. Gridline graphs: a review in two dimensions and an extension to higher dimensions. Discrete Appl. Math., 126(2-3):223-239, 2003. Google Scholar
  47. Svatopluk Poljak and Aleš Pultr. Representing graphs by means of strong and weak products. Comment. Math. Univ. Carolin., 22(3):449-466, 1981. Google Scholar
  48. Svatopluk Poljak, Vojtěch Rödl, and Aleš Pultr. On a product dimension of bipartite graphs. J. Graph Theory, 7(4):475-486, 1983. Google Scholar
  49. Pavan Sangha and Michele Zito. Finding large independent sets in line of sight networks. In Daya Ram Gaur and N. S. Narayanaswamy, editors, Algorithms and Discrete Applied Mathematics - Third International Conference, CALDAM 2017, Sancoale, Goa, India, February 16-18, 2017, Proceedings, volume 10156 of Lecture Notes in Computer Science, pages 332-343. Springer, 2017. Google Scholar
  50. William Staton and G. Clifton Wingard. On line graphs of bipartite graphs. Util. Math., 53:183-187, 1998. Google Scholar
  51. Douglas B. West. Introduction to Graph Theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact