On the Path Sequence of a Graph

Sławomir Bakalarski,

Jakub Zygadło


A subset S of vertices of a graph G = (V,E) is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from S. Denote by Ψk (G) the minimum cardinality of a k-path vertex cover in G and form a sequence Ψ (G) = (Ψ1 (G), Ψ2 (G), . . . , Ψ|V| (G)), called the path sequence of G. In this paper we prove necessary and sufficient conditions for two integers to appear on fixed positions in Ψ(G). A complete list of all possible path sequences (with multiplicities) for small connected graphs is also given.

Słowa kluczowe: k-path vertex cover, path sequence, list for small graphs
[1] Acharya H.B., Choi T., Bazzi R.A., Gouda M.G., The K-Observer Problem in Computer Networks. In: Stabilization, Safety and Security of Distributed Systems, Lecture Notes in Computer Science, Springer, Berlin-Heidelberg, 2011, 6976, pp. 5–18.
[2] Bollob´as B., Modern Graph Theory, GTM 184, Springer-Verlag, New York 2002.
[3] Breˇsar B., Kardoˇs F., Katreniˇc J., Semaniˇsin G., Minimum k-path vertex cover, Discrete Applied Mathematics, 2011, 159(12), pp. 1189–1195.
[4] Breˇsar B., Jakovac M., Katreniˇc J., Semaniˇsin G., Taranenko A., On the vertex k-path cover, Discrete Applied Mathematics, 2013, 161(13–14), pp. 1943–1949.
[5] Bullock F., Frick M., Semaniˇsin G., Vlaˇcuha R., Nontraceable detour graphs. Discrete Mathematics, 2007, 307(7-8), pp. 839–853.
[6] Courcelle B., The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Information and Computation, 1990, 85(1), pp. 12–75.
[7] Dinur I., Guruswami V., Khot S., Regev O., A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. SIAM Journal on Computing, 2005, 34(5), pp. 1129–1146.
[8] Dinur I., Safra S., On the hardness of approximating minimum vertex cover. Annals of Mathematics Second Series, 2005, 162(1), pp. 439–485.
[9] Funke S., Nusser A., Storandt S., On k-Path Covers and their Applications. Proceedings of the VLDB Endowment, 2014, 7(10), pp. 893–902.
[10] Jakovac M., The k-path vertex cover of rooted product graphs. Discrete Applied Mathematics, 2015, 187, pp. 111–119.
[11] Jakovac M., Taranenko A., On the k-path vertex cover of some graph products. Discrete Mathematics, 2013, 313(1), pp. 94–100.
[12] Kardoˇs F., Katreniˇc J., Schiermeyer I., On computing the minimum 3-path vertex cover and dissociation number of graphs. Theoretical Computer Science, 2011, 412(50), pp. 7009–7017.
[13] Li Y., Tu J., A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs. International Journal of Computer Mathematics, 2014, 91(10), pp. 2103–2108.
[14] McKay B., Home page at the Research School of Computer Science, Australian National University. Accessed July 22, 2015, https://cs.anu. edu.au/people/Brendan.McKay/data/graphs.html.
[15] Novotny´ M., Design and Analysis of a Generalized Canvas Protocol. In: Information Security Theory and Practices. Security and Privacy of Pervasive Systems and Smart Devices, Lecture Notes in Computer Science vol. 6033, Springer Berlin Heilderberg, 2010, pp. 106–121.
[16] Tu J., Yang F., The vertex cover P3 problem in cubic graphs. Information Processing Letters, 2013, 113(13), pp. 481–485.
[17] Tu J., Zhou W., A factor 2 approximation algorithm for the vertex cover P3 problem. Information Processing Letters, 2011, 111(14), pp. 683–686.
[18] Tu, J., Zhou, W., A primal-dual approximation algorithm for the vertex cover P3 problem, Theoretical Computer Science, 2011, 412(50), pp. 7044–7048.
[19] Wolfram Research, Inc., Mathematica, Version 10.0, Champaign, IL (2014).
[20] Zygadl o J., Home page at the Institute of Computer Science and Computational Mathematics, Jagiellonian University. http://www.ii.uj.edu.pl/˜zygadlo/psiksource.zip.