On the Path Sequence of a Graph

• Autorzy: Bakalarski, S. , Zygadło, J.
• Języki publikacji: EN

Abstrakty

EN

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), ѱ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

EN

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

• Czasopismo: Schedae Informaticae
• Rocznik: 2015
• Tom: Vol. 24
• Strony: 239--251
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Bakalarski, S.

• Institute of Computer Science and Computational Mathematics Faculty of Mathematics and Computer Science, Jagiellonian University ul. Łojasiewicza 6, 30-348 Kraków, Poland

autor

Zygadło, J.

• Institute of Computer Science and Computational Mathematics Faculty of Mathematics and Computer Science, Jagiellonian University ul. Łojasiewicza 6, 30-348 Kraków, Poland

Bibliografia

• [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ás B., Modern Graph Theory, GTM 184, Springer-Verlag, New York 2002.
• [3] Brešar B., Kardoš F., Katrenič J., Semanišin G., Minimum k-path vertex cover, Discrete Applied Mathematics, 2011, 159(12), pp. 1189–1195.
• [4] Brešar B., Jakovac M., Katrenič J., Semanišin 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šin G., Vlačuha 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š F., Katrenič 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] Zygadło J., Home page at the Institute of Computer Science and Computational Mathematics, Jagiellonian University. http://www.ii.uj.edu.pl/˜zygadlo/psiksource.zip.

Identyfikatory

DOI

10.4467/20838476SI.16.020.4361