×
Schauerte, Boris; Zamfirescu, Carol T.

Small \(k\)-pyramids and the complexity of determining \(k\). (English) Zbl 1320.05130

J. Discrete Algorithms 30, 13-20 (2015).
Summary: Motivated by the computational complexity of determining whether a graph is Hamiltonian, we study under algorithmic aspects a class of polyhedra called \(k\)-pyramids, introduced in [C. T. Zamfirescu and T. I. Zamfirescu, Math. Nachr. 284, No. 13, 1739–1747 (2011; Zbl 1236.05121)], and discuss related applications. We prove that determining whether a given graph is the 1-skeleton of a \(k\)-pyramid, and if so whether it is belted or not, can be done in polynomial time for \(k \leq 3\). The impact on Hamiltonicity follows from the traceability of all 2-pyramids and non-belted 3-pyramids, and from the hamiltonicity of all non-belted 2-pyramids. The algorithm can also be used to determine the outcome for larger values of \(k\), but the complexity increases exponentially with \(k\). Lastly, we present applications of the algorithm, and improve the known bounds for the minimal cardinality of systems of bases called foundations in graph families with interesting properties concerning traceability and Hamiltonicity.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C45 Eulerian and Hamiltonian graphs

Keywords:

pyramid; prism; Halin graph; Hamiltonian

Citations:

Zbl 1236.05121
PDF BibTeX XML Cite
\textit{B. Schauerte} and \textit{C. T. Zamfirescu}, J. Discrete Algorithms 30, 13--20 (2015; Zbl 1320.05130)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Aldred, R. E.L.; Bau, S.; Holton, D. A.; McKay, B. D., Nonhamiltonian 3-connected cubic planar graphs, SIAM J. Discrete Math., 13, 1, 25-32, (2000) · Zbl 0941.05041
[2] Berge, C., Theory of graphs and its applications, (1962), Methuen London · Zbl 0097.38903
[3] Bondy, J. A., Pancyclic graphs: recent results, Colloq. Math. Soc. János Bolyai, 10, 181-187, (1975) · Zbl 0324.05115
[4] Boyer, J. M.; Myrvold, W. J., On the cutting edge: simplified \(O(n)\) planarity by edge addition, J. Graph Algorithms Appl., 8, 3, 241-273, (2004) · Zbl 1086.05067
[5] Brandstädt, A.; Chepoi, V. D.; Dragan, F. F., The algorithmic use of hypertree structure and maximum neighbourhood orderings, Discrete Appl. Math., 82, 1-3, 43-77, (1998) · Zbl 0893.05018
[6] Broersma, H. J.; Kloks, T.; Kratsch, D.; Müller, H., Independent sets in asteroidal triple-free graphs, (Proc. 24th Int. Colloq. Automata, Languages and Programming, Lect. Notes Comput. Sci., vol. 1256, (1997), Springer), 760-770 · Zbl 1401.05278
[7] Chang, M. S., Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput., 27, 6, 1671-1694, (1998) · Zbl 0911.05051
[8] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to algorithms, (2009), MIT Press and McGraw-Hill · Zbl 1187.68679
[9] Corneil, D. G.; Perl, Y., Clustering and domination in perfect graphs, Discrete Appl. Math., 9, 27-40, (1984) · Zbl 0581.05053
[10] Farber, M., Independent domination in chordal graphs, Oper. Res. Lett., 1, 134-138, (1982) · Zbl 0495.05053
[11] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039
[12] Garey, M. R.; Johnson, D. S.; Tarjan, R. E., The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 704-714, (1976) · Zbl 0346.05110
[13] Gaspers, S.; Liedloff, M., A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs, (2007), Univ. Bergen, Technical Report no. 344
[14] Grinstead, D. L.; Slater, P. J., A recurrence template for several parameters in series-parallel graphs, Discrete Appl. Math., 54, 151-168, (1994) · Zbl 0812.68099
[15] Holton, D. A.; McKay, B. D., The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Comb. Theory, Ser. B, 45, 305-319, (1989) · Zbl 0607.05051
[16] Irving, R. W., On approximating the minimum independent dominating set, Inf. Process. Lett., 37, 197-200, (1991) · Zbl 0713.68033
[17] Kahng, A. B.; Park, C.-H.; Xu, X., Fast dual-graph-based hotspot filtering, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 27, 9, (2008)
[18] Karp, R. M., Reducibility among combinatorial problems, 85-103, (1972), Plenum Press New York
[19] Knuth, D., The art of computer programming, vol. 3: sorting and searching, (1997), Addison-Wesley, Section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging · Zbl 0883.68015
[20] Kratsch, D.; Stewart, L., Domination on cocomparability graphs, SIAM J. Discrete Math., 6, 400-417, (1993) · Zbl 0780.05032
[21] Liu, C.; Song, Y., Exact algorithms for finding the minimum independent dominating set in graphs, (ISAAC 2006, Lect. Notes Comput. Sci., vol. 4288, (2006), Springer), 439-448 · Zbl 1135.05315
[22] Malik, S.; Qureshi, A. M.; Zamfirescu, T., Hamiltonian properties of generalized halin graphs, Can. Math. Bull., 52, 3, 416-423, (2009) · Zbl 1171.05031
[23] Manlove, D. F., On the algorithmic complexity of twelve covering and independence parameters of graphs, Discrete Appl. Math., 91, 1-3, 155-175, (1999) · Zbl 0922.05041
[24] Pfaff, J.; Laskar, R.; Hedetniemi, S. T., Linear algorithms for independent domination and total domination in series-parallel graphs, Congr. Numer., 45, 71-82, (1984) · Zbl 0571.05045
[25] Skowrońska, M., Hamiltonian properties of halin-like graphs, Ars Comb., 16(B), 97-109, (1983) · Zbl 0545.05043
[26] Skowrońska, M.; Sysło, M. M., Hamiltonian cycles in skirted trees, Zastos. Mat., 19, 3-4, 599-610, (1987) · Zbl 0719.05045
[27] Skupień, Z., Crowned trees and planar highly Hamiltonian graphs, 537-555, (1990), Wissenschaftsverlag Mannheim · Zbl 0717.05029
[28] Steinitz, E., Polyeder und raumeinteilungen, Geometrie, vol. 3, 1-139, (1922)
[29] Wiener, G.; Araya, M., On cubic planar Hypohamiltonian and hypotraceable graphs, Electron. J. Comb., P85, 1-11, (2011) · Zbl 1217.05065
[30] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. Appl. Math., 38, 364-372, (1980) · Zbl 0455.05047
[31] Zamfirescu, C. T.; Zamfirescu, T. I., Hamiltonian properties of generalized pyramids, Math. Nachr., 284, 13, 1739-1747, (2011) · Zbl 1236.05121
[32] Zamfirescu, T., Three small cubic graphs with interesting Hamiltonian properties, J. Graph Theory, 4, 287-292, (1980) · Zbl 0442.05047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.