A graph is Konig for a q-path if every its induced subgraph has the following property. The maximum number of pairwise vertex-disjoint induced paths each on q vertices is equal to the minimum number of vertices, such that removing all the vertices produces a graph having no an induced path on q vertices. In this paper, for every q 5, we describe all Konig graphs for a qpath obtained from forests and simple sycles by replacing some vertices into graphs not containing induced paths on q vertices.
require the equality of the parameters in all induced subgraphs of a graph. Thus, the class of bipartite graphs coincides with the class of all Konig graphs for P2 in this sense.
A lot of papers on the F -matching problem are devoted to algorithmic aspects (see
[
It seems perspective to nd new polynomially solvable cases for the F -matching
and F -cover problems in the context of the method of critical graph classes developed
in the papers of V. E. Alekseev and D. S. Malyshev [
Being formulated as the integer linear programming problems, the F -matching and
F -cover problems form a pair of dual problems. So, Konig graphs are graphs, such that
for any their induced subgraph there is no a duality gap for the problems above. In
this regard, Konig graphs are similar to perfect graphs having the same property with
respect to another pair of dual problems (vertex coloring and maximum clique) [
Every hereditary class X can be described by a set of its minimal forbidden induced
subgraphs, i.e. minimal by the relation \to be an induced subgraph" graphs not
belonging to X . A class K(F ) is hereditary for any F and therefore it can be described
by a set of forbidden induced subgraphs. Such a characterization for K (P2) is given
by the Konig theorem. In addition to this classical theorem, the following results are
known. All minimal forbidden induced subgraphs for the class K(C) are described in
[
The aim of this paper is to extend the structural description in [
In what follows we consider induced Pq with q 5. The maximum number of subgraphs in Pq-matchings of G is denoted as Pq (G), and the minimum number of vertices in its Pq-covers as Pq (G).
A q-path is an induced subgraph isomorphic to Pq. We denote by (v1; v2; : : : ; vq) a q-path that consists of vertices v1; v2; : : : ; vq. We denote by Fq the class of graphs not containing q-paths.
We denote by jGj the number of vertices in G. We denote by N (x) the neighbourhood of a vertex x in a graph.
We denote by G [ H the graph obtained from graphs G and H with non-intersected sets of vertices by their union. We denote by G v the graph obtained from G by deleting a vertex v with all incident edges.
Considering a cycle Cn, we assume that its vertices are clockwisely numbered as 0; 1; :::; n 1. The arithmetic operations with the vertex numbers are performed modulo n. Every residue class of vertex numbers for modulo q is called a q-class. 2
In this section, we de ne the R-Fq-extention of graphs and describe the basic properties of graphs obtained by this procedure.
De nition 1. The operation of replacement of a vertex x in a graph G with a graph H, where V (G) \ V (H) = ;, consists of the following. We take a graph (G x) [ H and add all edges connecting V (H) with N (x).
A homogeneous set in a graph G is a set A V (G), such that every vertex of V (G)nA is either adjacent to all vertices of A or to none of them. A homogeneous set is trivial if it is equal to V (G) or consists of one vertex and non-trivial, otherwise. De nition 2. Let X be a class of graphs. The operation of a R-X -extention of G consists of the following. Every vertex of degree 1 or 2 is replaced with an arbitrary graph of X .
De nition 3. A section with a base x denoted by S(x) is the set of vertices of the graph by which we replaced x. Every vertex not replaced with any graph is considered as a separate section.
Obviously, any section is a homogeneous set. A section is trivial if it consists of one vertex and non-trivial, otherwise.
We say that two sections S(x) and S(y) are adjacent in a R-Fq-extention of a graph G if x and y are adjacent in G. Obviously, if S(x) and S(y) are adjacent, then each vertex of S(x) is adjacent to each vertex of S(y).
Lemma 1. If a set of vertices A induce Pq in a R-Fq-extention of a graph G, then jA \ S(x)j = 1 for all x 2 V (G).
Proof. Every section induces a subgraph from Fq. Then the set A can not be entirely contained in any section. Since any section is a homogeneous set, if a section S(x) contains two or more vertices of A, then the set A\S(x) is a non-trivial homogeneous set in the subgraph induced by A. But a q-path does not contain a non-trivial homogeneous set for any q > 3.
Lemma 2. Every minimum Pq-cover of any R-Fq-extention of any graph consists of whole sections.
Proof. Let C be a minimum Pq-cover of an R-Fq-extention of some graph G. Suppose that there exists a section which contains vertices x 2 C and y 62 C. Since C is a minimum Pq-cover, there exists a set A V (G) inducing Pq, such that A \ C = fxg. Otherwise, the vertex x can be deleted from C. By Lemma 1, y 62 A. But then Anfxg [ fyg induce Pq, but it does not contain vertices of C.
In this section, we consider graphs obtained by a R-Fq-extention of forests. We will prove that all such graphs are Konig for Pq.
Theorem 1. For any q, every R-Fq-extention F~ of a forest F is a Konig graph for Pq.
Proof. The proof is by induction on the number of q-paths in F~. If there is no a q-path, then Pq (F~) = Pq (F~) = 0. Now consider F~ which contains at least one q-path. By Lemma 1, all vertices of this q-path are contained in di erent sections. Obviously, they induce Pq in F .
Let T be a connected component of F containing a q-path. Let us select an arbitrary root r of T having degree three or more, if one exists. If T is a simple path, then r is one of its leaves.
Speaking about trees, we consider that they are drawn in a bottom-up manner from roots to leaves. For every q-path in T , a bottom vertex is the closest to r vertex of this q-path. Let a be the farther from r bottom vertex for all q-paths. There exists a q-path X which consists of a and descendants of a. Let T 0 be a subtree of T with the root a. Then in T 0 every q-path contains the vertex a.
Let X = fx1; : : : ; xkg be a set of vertices inducing Pq in T with the bottom vertex a. Obviously, a is a member of this set. Let us select an arbitrary vertex yi in every section S(xi). It is easy to see that Y = fy1; : : : ; ykg induce Pq in F~. Delete all vertices of Y from F~. Denote obtained graph as F~0 . It contains less q-paths than F~. By the induction hypothesis, there exists a Pq-matching M of F~0 and its Pq-cover C, such that jP j = jCj. Then M [ fY g is the Pq-matching of F~ of the cardinality jM j + 1.
For a Pq-cover of F~, we have two cases: 1. C contains at least one of the sections S0 (x1); : : : ; S0 (xk), where S0 (xi) = S(xi)nfyig. Suppose that C contains sections S0 (xi) and S0 (xj ), where i 6= j. If the vertex xi is an ancestor of xj in the tree T , then every q-path, intersected with S0 (xj ) intersects S0 (xi) as well. Therefore, CnS0 (xj ) is a Pq-cover of F~0. Now suppose that xi; xj are not ancestors of each other. Then they have a common ancestor xl in T . Obviously, xl is a descendant of a or equals to a. Since degree of xl is three or more, jS (xl) j = 1. In this case, every q-path intersected with S0 (xi) or S0 (xj ) contains xl. Therefore, Cn S0 (xi) [ S0 (xj ) [ fxlg is a Pq-cover of the graph F~0 .
Thus, if C is a minimum Pq-cover of the graph F~0 , then C contain exactly one of the sections S0 (x1); : : : ; S0 (xk). Let S0 (xi) be a such section. Then C [ fyig is a Pq-cover of F~. 2. None of the sections S0 (x1); : : : ; S0 (xk) is a subset of C. Then at least one of S0 (x1); : : : ; S0 (xk) is empty. Let b denote the highest common ancestor of xi with S0 (xi) = ;. Then either b = a or b is a descendant of a and every section between a and b consists of more than one vertex. In the both cases, every q-path of F~ with bottom vertex in S(a) contains the vertex b and other q-paths are covered by the set C. Thus, C [ fbg is a Pq-cover of F~.
So, for the both cases, there exists a Pq-cover of the graph F~ of the cardinality jM j+ 1. But, every induced subgraph of F~ is an R-Fq-extention of some forest. Therefore, F~ is a Konig graph for Pq. 4 4.1
Common cases for forbidden induced graphs Now we consider the graphs obtained by applying a R-Fq-extention to simple cycles. We call them R-Fq-extended cycles.
Considering a R-Fq-extention of a cycle Cn, we assume that the sections are clockwisely numbered as 0; 1; :::; n 1. Every residue class of sections numbers for modulo q is called a q-class.
At rst, we de ne several in nite families of forbidden induced subgraphs for K(Pq) for every q 5.
Obviously, for any k > 1 pack (Cqk) =
Pq (Cqk+1) = cover (Cqk) =
Pq (Cqk 1) = = =
Pq (Cqk+q 1) = k; Pq (Cqk q+1) = k: Note that every proper induced subgraph of a simple cycle is a forest. By Theorem 1, it is a Konig graph for Pq. Hence, the following lemma is valid.
Lemma 3. A cycle Cn belongs to K(Pq) if n is divisible by q, and Cn is a minimal forbidden induced subgraph for K(Pq) if n is not divisible by q.
Thus, a R-Fq-extention of a simple cycle can be a Konig graph for Pq only if the basic cycle has a number of vertices divisible by q.
Let k1; k2; : : : ; kq be arbitrary naturals, such that k1 + k2 + + kq = qn. Let us chose q vertices in a cycle Cqn in such a way that its paths containing no the chosen vertices except their endpoints have lengths k1; k2; : : : ; kq. We replace any chosen vertex into an arbitrary two-vertex graph. The set of all resultant graphs is denoted by D~q (k1; k2; : : : ; kq). Let Dq (k1; k2; : : : ; kq) denote any graph of the set D~q (k1; k2; : : : ; kq).
Let denote ri = Pij=1 kj . Obviously, one can enumerate vertices along the cycle in such a way that the replaced vertices have numbers 0; r1; : : : rq 1.
De nition 4. A graph D(k1; k2; : : : ; kq) is crowded if 8i; j : ri 6 rj (mod q). It means that exactly one vertex is replaced with a two-vertex graph in every q-class of the basic cycle.
De nition 5. A T-array in a R-Fq-extended cycle is a maximal collection of sequentially adjacent trivial sections. Similarly, a N-array in a R-Fq-extended cycle is a maximal collection of sequentially adjacent non-trivial sections. A size of a T-array or a N-array is a number of sections in it. De nition 6. A vector of array sequence (AS-vector for short) of a graph Dq (k1; k2; : : : ; kq) is a sequenced collection of numbers (u1; t1; u2; t2; : : : ; um; tm), where for all i 2 f1; : : : ; mg ti is lenght of T-array and ui is lenght of N-array.
For example, the AS-vector for the graph (3; 2; 2; 15; 1; 9; 1; 6; 1; 14; 1; 18).
Note that AS-vector of every graph Dq (k1; k2; : : : ; kq) has the properties:
The arithmetic operations with the indexes in an AS-vector are performed modulo Theorem 2. A crowded graph Dq (k1; k2; : : : ; kq) is a minimal forbidden induced subgraph for K(Pq) if and only if for its AS-vector (u1; t1; u2; t2; : : : ; um; tm) there exists a number i, such that ui + ti + ui+1 6 0 (mod q).
Proof. For every crowded graph D, Pq (D) = n + 1, where qn is length of the basic cycle. We show that for every crowded graph D Pq (D) = n + 1 if and only it in its AS-vector for every i ui + ti + ui+1 is divisible by q and Pq (D) = n, otherwise.
Let Dq (k1; k2; : : : ; kq), where k1 + k2 + + kq = qn, be a crowded graph. Its number of vertices equals to qn + q. It means that a Pq-matching of the cardinality n + 1 must include all vertices of the graph. It is easy to see that every N-array have to begin one of q-paths and end one of q-path of such Pq-matching. In other words, it can not lie in the middle of any q-path of the Pq-matching. Moreover, if the end of a q-path of the Pq-matching belongs to a trivial section, then the beginning of the next q-path belongs strictly to the next section. It is possible only if the number of sections between the beginning of a N-array and the end of the next one is divisible by q, i.e. 8i ui + ti + ui+1 = q. Otherwise, no one Pq-matching includes all vertices of the graph and the maximum cardinality of Pq-matchings is equal to n.
Every induced subgraph of a crowded graph is a R-Fq-extended forest or a R-Fqextended cycle, such that one of its q-classes consists of trivial sections only. In the both cases, the graph is Konig for Pq. So, every crowded graph D with Pq (D) = n is a minimal forbidden induced subgraph for K(Pq).
Notice that for every q 3 the minimum number of sections in crowded graphs is equal to 2q. For example, for any odd q a graph Dq(2; 2; : : : ; 2) (Fig. 1) has the minimum possible number of sections. Similarly, for every even q, a graph Dq(2; 2; : : : ; 2; 1; 2; 2; : : : ; 2; 3) is also extremal. By Theorem 2, for any q 5, this | q2{z1 } | q2{z1 } graphs are minimal forbidden induced subgraphs for K(Pq). For every Pq, let Dq denote the set of the crowded graphs that are minimal forbidden induced subgraphs for K(Pq).
Now we prove that Dq is a complete set of forbidden induced subgraphs for R-Fqextended cycles, which are Konig graphs for Pq.
Theorem 3. A R-Fq-extended cycle is a Konig graph for Pq if and only if it does not include induced subgraphs belonging to the set Dq.
Proof. Let G be obtained from a simple cycle Cqn by replacing its vertices with Fqgraphs, and any its induced subgraph does not belong to the set Dq. By Theorem 1, any R-Fq-extended tree it is Konig for P4. Every induced subgraph of G is a R-Fq-extended cycle with the same property or an R-Fq-extended tree. Thus, it is enough to prove that there exist a Pq-matching and a Pq-cover of equal cardinalities in G.
The proof is by induction on the number of q-paths in the graph. Let every q-path in G intersect at least one trivial section. It means that deleting a q-path always induce a R-Fq-extended forest. The following cases are possible. 1. G does not contain induced crowded graphs. Then there is at least one q-class consisting of only trivial sections. Obviously, this q-class gives a Pq-cover of G of the cardinality q. A Pq-matching of the same cardinality coincides with one of the maximum Pq-matchings of the basic cycle. 2. G contains N-array of lenght q 1. Let it consist of the sections S1; S2; : : : ; Sq 1.
Then we consider a graph G0 obtained from G by deletion of sections S0; S1; : : : ; Sq. The graph G0 is a R-Fq-extended tree. Therefore, by Theorem 1, there exist a Pqmatching M 0 and a Pq-cover C0 of G0 of equal cardinalities. In what follows, for each i 2 f0; nq 1g, let ui denote an arbitary vertiex of a section Si, and vi denote an another vertex of the same section, if one exists. It is easy to see that M = M 0 [ f(u0; u1; : : : uq 1) ; (v1; v2; : : : vq 1; uq)g is the Pqmatching of graph G, and C = C0 [ S0 [ Sq is its Pq-cover and jM j = jCj = M 0 + 2 3. G contains a crowded induced subgraph and the maximum size l of N-arrays is more than 2 and no more than q 2. Suppose that a N-array of the maximum size consists of sections S1; S2; : : : ; Sl. Assume that a section Sqi+2 is non-trivial for some i 1. Then G contains a crowded induced subgraph, such that its AS-vector contains a sequence uj ; tj ; uj+1, where uj = 1, tj = 1, uj+1 = l 2. The sum of this parameters is l. By Theorem 2, such graph must be forbidden. Thus, sections Sq+2; S2q+2; : : : S(n 1)q+2 are trivial. Note that sections S0 and Sl+1 are trivial as well. Let us consider a set
C = n 1 [ Sqi+2 [ S0 [ Sl+1: i=1 It is easy to see that C is a Pq-cover of G and jCj = n + 1. But none crowded induced subgraph of G is forbidden. Therefore, by proof of Theorem 2, it contains a Pq-matching M of the cardinality n + 1. Obviously, M is a Pq-matching of graph G. 4. G contains a crowded induced subgraph and every N-array of G consists of no more than 2 sections. Consider two neighbour N-arrays of some crowded subgraph D of G. Let the rst of them begin from S1. It means that the section S1 of the graph G is non-trivial. By Theorem 2, the next N-array ends in section, which number is divisible by q. In other words, for G there exists l, such that Sql is non-trivial. Let l > 1. Consider a graph D0 obtained from D by adding a vertex into the section Sq+3 and deleting one vertex from the non-trivial section of the same q-class. The AS-vector of the graph D0 contains a sequence ui; ti; ui+1, such that their sum is equal to q + 3. By Theorem 2, D0 must be forbidden. Thus, the section Sq+3 is trivial in G. Similarly, all sections S2q+3; S3q+3; : : : S(l 1)q+3 are trivial in G. Since every N-array consists of no more than 2 sections, the section S3 is trivial as well. Similarly, if Sr is the begin section of some N-array of a crowded induced subgraph of G and Sr+x is the begin section of its next N-array, then for 0 < x hq 2 < q, all sections Sr+2; Sr+q+2; : : : Sr+hq+2 of the graph G are trivial. By Theorem 2, x q 1(mod q) if the N-array consists of one section or x q 2(mod q) if it consists of two sections.
Consider an AS-vector (u1; t1; u2; : : : ; um; tm) of the graph D. Let u1 correspond to the N-array, which begins from the section S1. Denote r0 = 1, ri = ri 1 + ui + ti for all i 2 f1; : : : ; m 1g, hi is the number, such that 0 < ri+1 ri hiq 2 < q. It is easy to see that
m hi C = [ [ Sri+jq+2
i=0 j=0 is a P q-cover of the graph G and jCj = n+1. But none crowded induced subgraph of G is forbidden. Therefore, by proof of Theorem 2, it contains a Pq-matching M of the cardinality n + 1. Obviously, M is a Pq-matching of the graph G.
Thus, if every q-path of the graph G intersects at least one trivial section, then G is a Konig graph for Pq.
Now let some q-path of the graph G intersect only non-trivial sections. Since for q 5, there exists a crowded forbidden graph having 2q sections, every R-Fq-extended cycle, which consists of only non-trivial sections, contains a crowded forbidden induced subgraph. Thus, G contains at least one trivial section. Suppose that S0 is a trivial section and S1; S2; : : : ; Sq are non-trivial sections in G.
Let us select one vertex vi from each section Si, i 2 f1; : : : ; qg. Let G0 denote a graph obtained from G by deleting vertices v1; v2; : : : ; vq. By the induction hypothesis, G0 contains a Pq-matching M 0 and a Pq-cover C0 of equal cardinalities. Note that C0 caorenttawinossuatchlesaescttoionnes,setchteinonSa0 misonnogtSai nsufbvsiegt; oif2Cf0 1.;O: t: h:e;rqwg,isbeuCtn0oismnootremtihnaimnu2.mI.f Tthheerne we change section with the minimum number into S0 in C0 . The obtained Pq-cover is a minimum Pq-cover, which contains exactly one section among Sin fvig ; i 2 f1; : : : ; qg. We add to C0 the deleted vertex of the corresponding section. We add to M 0 the qpath (v1; v2; : : : ; vq). The obtained sets are some Pq-cover and some Pq-matching of the graph G of equal cardinalities.