On the Path Sequence of a Graph

Sławomir Bakalarski; Jakub  Zygadło

Titles

Abstract

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) = (Ψ₁ (G), Ψ₂(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.

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) = (Ψ₁(G), Ψ₂(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.

Keywords

k-path vertex cover, path sequence, list for small graphs

References

[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.

Information

Information: Schedae Informaticae, 2015, Volume 24, pp. 239 - 251

DOI: https://doi.org/10.4467/20838476SI.16.020.4361

Article type: Original article

Titles:

Polish:

On the Path Sequence of a Graph

English:

On the Path Sequence of a Graph

Authors

Sławomir Bakalarski

Jagiellonian University in Kraków, Gołębia 24, 31-007 Kraków, Poland

Jakub Zygadło

Faculty of Mathematics and Computer Science, Jagiellonian University, Krakow, Poland

Published at: 11.04.2016

Article status: Open

Licence: None

Percentage share of authors:

Sławomir Bakalarski (Author) - 50%

Jakub Zygadło (Author) - 50%

Article corrections:

-

Publication languages:

English

View count: 2245

Number of downloads: 1918

<p> On the Path Sequence of a Graph</p>

Pobierz pełny tekst

Titles

Abstract

Keywords

References

Information

Authors