- Tytuł:
- On the Path Sequence of a Graph
- Autorzy:
-
Bakalarski, Sławomir
Zygadło, Jakub - Powiązania:
- https://bibliotekanauki.pl/articles/1373669.pdf
- Data publikacji:
- 2015
- Wydawca:
- Uniwersytet Jagielloński. Wydawnictwo Uniwersytetu Jagiellońskiego
- Tematy:
-
$k$-path vertex cover
path sequence
list for small graphs - Opis:
- 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 $psi_k(G)$ the minimum cardinality of a $k$-path vertex cover in $G$ and form a sequence $\psi(G) = (\psi_1 (G), \psi_2 (G), . . . , \psi_{|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 $\psi(G)$. A complete list of all possible path sequences (with multiplicities) for small connected graphs is also given.
- Źródło:
-
Schedae Informaticae; 2015, 24; 239-251
0860-0295
2083-8476 - Pojawia się w:
- Schedae Informaticae
- Dostawca treści:
- Biblioteka Nauki
Artykuł