# Decomposition of Graphs into Paths and Cycles

Authors: S. Arumugam; I. Sahul Hamid; V. M. Abraham
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

Adecomposition of a graph G  is a collection ψ of edge-disjoint subgraphs H1,H2,…,Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is a path or a cycle in G, then ψ is called a path decomposition of G. If each Hi is a path in G, then ψ is called an acyclic path decomposition of G. The minimum cardinality of a path decomposition (acyclic path decomposition) of G is called the path decomposition number (acyclic path decomposition number) of G and is denoted by
π(G) (πa(G)). In this paper we initiate a study of the parameter π and
determine the value of π for some standard graphs. Further, we obtain
some bounds for π and characterize graphs attaining the bounds. We
also prove that the difference between the parameters π
and πa can be made arbitrarily large.


---

## Body

## 1. Introduction

Graph decomposition problems rank among the most prominent areas of research in graph theory and combinatorics and further it has numerous applications in various fields such as networking, block designs, and bioinformatics.Adecomposition of a graph G is a collection of edge-disjoint subgraphs H1,H2,…,Hr of G such that every edge of G belongs to exactly one Hi. Various types of path decompositions and corresponding parameters have been studied by several authors by imposing conditions on the paths in the decomposition. It is obvious that every graph admits a decomposition in which each subgraph Hi is either a path or a cycle. In this connection, Erdo¨s asked what is the minimum number of paths into which every connected graph on n vertices can be decomposed and Gallai conjectured that this number is at most ⌈n/2⌉ as stated below.Gallai's Conjecture(see  [1]).  If G is a connected graph on n vertices, then G can be decomposed into ⌈n/2⌉ paths.A good number of research articles have been published in which Gallai's is the focus of study and still this conjecture remains unsettled for more than 30 years. Towards a proof of the conjecture, Lovasz [1] made the first significant contribution by proving the following theorem.Theorem 1 (see [1]).
A graphG on n vertices (not necessarily connected) can be decomposed into ⌊n/2⌋ paths and cycles.Gallai's conjecture and Theorem1 motivate the following definition.Definition 2.
Letψ={H1,H2,…,Hr} be a decomposition of a graph G. If each Hi is either a path or a cycle, then ψ is called a path decomposition of G. If each Hi is a path, then ψ is called an acyclic path decomposition of G. The minimum cardinality of a path decomposition of G is called the path decomposition number. Similarly the acyclic path decomposition number of G is defined and is denoted by πa(G).The parameterπa was introduced by Harary and further studied extensively by Harary and Schwenk [2], Péroche [3], Stanton et al. [4, 5], and Arumugam and Suseela [6]. This paper initiates a study of the parameter path decomposition number.


## 2. Basic Terminologies and Results

By a graphG=(V,E) we mean a finite, connected, and undirected graph without loops or multiple edges. For graph theoretic terminology we refer to Chartrand and Lesniak [7]. The order and size of a graph are denoted by n and m, respectively.IfP=(v1,v2,…,vr) is a path in a graph G, then the vertices v2,v3,…,vr-1 are called internal vertices of P and v1 and vr are called external vertices of P. For a cycle C=(v1,v2,…,vr,v1), the vertex v1 is called the initial vertex and all other vertices are internal vertices. Two paths P and Q of a graph G are said to be internally disjoint if no vertex of G is an internal vertex of both P and Q. If P=(v0,v1,v2,…,vr) and Q=(vr=w0,w1,w2,…,ws) are two paths in G, then the walk obtained by concatenating P and Q at vr is denoted by P∘Q, that is, P∘Q=(v0,v1,…,vr=w0,w1,…,ws). Further when P=(v1,v2,…,vn), the path (vn,vn-1,…,v1) is denoted by P-1.Acaterpillar is a tree in which removal of all the pendant vertices results in a path. For vertices x and y in a connected graph G, the detour distanceD(x,y) is the length of a longest x-y path in G. The detour diameterD of G is defined to be D=max{D(x,y):x,y∈V(G)}. Two graphs are said to be homeomorphic if both can be obtained from the same graph by a sequence of subdivisions of edges. The length of a longest cycle in a graph G is called the circumference of G.We need the following theorems.Theorem 3 (see [4]).
For any treeT, πa(T)=k/2, where k is the number of vertices of odd degree.Theorem 4 (see [6]).
LetG be a unicyclic graph with cycle C. Let r denote the number of vertices of degree greater than two on C. Let k denote the number of vertices of odd degree. Then
(1)πa(G)={2ifr=0,k2+1ifr=1,k2otherwise.Theorem 5 (see [2]).
For the complete graphKn, one has πa(Kn)=⌈n/2⌉.Theorem 6 (see [2]).
For the complete bipartite graphKr,s with r≤s, one has
(2)πa(Kr,s)={r+s2ifrsisodd,⌈rs2r-δ(r,s)⌉otherwise,
where δ(r,s) is the conventional Kronecker delta.


## 3. Bounds forπ

In this section we obtain some bounds for the path decomposition numberπ and characterize the graphs attaining some of the bounds obtained. Let us first establish an upper and lower bound involving the order of the graph and the number of vertices of odd degree. For this we define the term t(G) of a graph G. Given a path decomposition ψ for a graph G, let tψ=∑P∈ψt(P), where t(P) denotes the number of internal vertices of P. Now, define t(G)=maxtψ, where the maximum is taken over all path decompositions ψ of G.Theorem 7.
LetG be a graph on n vertices. Then k/2≤π(G)≤n/2, where k is the number of vertices of odd degree in G.Proof.
Let𝒫 be the collection of all path decompositions of G and let ψ∈𝒫.
Then(3)m=∑P∈ψ‍|E(P)|=∑P∈ψ‍(t(P)+1)=∑P∈ψ‍t(P)+|ψ|=tψ+|ψ|.
Hence, |ψ|=m-tψ  so that π=m-t. Also, it is not difficult to see that m=k/2+∑v∈V(G)⌊degv/2⌋ and hence π(G)=k/2+∑v∈V(G)⌊degv/2⌋-t, which implies that π(G)≥k/2. The upper bound follows immediately from Theorem 1.Remark 8.
IfG is a graph with k vertices of odd degree, then π(G)=k/2 if and only if there exists a path decomposition ψ of G such that every vertex v is an internal vertex of ⌊degv/2⌋ members in ψ.The following examples show that there are infinite families of graphs attaining the bounds given in the above theorem and consequently prove that these bounds are sharp. That is, the family of all trees and an infinite class of unicyclic graphs achieve the lower bound, whereas some common classes of graphs such as complete graphs, wheels, and complete bipartite graphs of odd size attain the upper bound. In this connection we need to note down the inequality thatπ(G)≤πa(G) which follows from the fact that every acyclic path decomposition of a graph is also a path decomposition.Example 9.
(i) For any treeT, π(T)=πa(T)=k/2.
(ii) IfG is a unicyclic graph with cycle C and if r denotes the number of vertices on C with degree greater than two, then
(4)π(G)={1ifr=0,k2+1ifr=1,k2otherwise.Proof.
(i)  Since every path decomposition ofT is an acyclic path decomposition of T, we have π(T)=πa(T) and hence the result follows from Theorem 3.
(ii)  Ifr=0, then G=C  so that π(G)=1. If r=1, then it follows from Theorem 4 that πa(G)=(k/2)+1 and hence π(G)≤πa(G)=k/2+1. Further, for any path decomposition ψ of G all the k odd vertices and at least one vertex on C are external vertices of some paths in ψ so that π(G)≥k/2+1. Thus π(G)=k/2+1. If r>1, by Theorem 4, we have πa(G)=k/2 and hence π(G)≤πa(G)=k/2. Thus π(G)=k/2 as π(G)≥k/2.Example 10.
(i)  For the complete graphKn, we have π(Kn)=⌊n/2⌋.
(ii)  For the complete bipartite graphKr,s with r≤s(5)π(Kr,s)={r+s2ifrsis  odd,⌈s2⌉otherwise,
(iii)  IfWn denotes the wheel on n vertices, then π(Wn)=⌊n/2⌋.Proof.
(i)  Letψ be any path decomposition of Kn. Since every member of ψ covers at most n edges, we have |ψ|≥⌊n/2⌋ so that π(Kn)≥⌊n/2⌋. Further, it follows from Theorem 1 that π(Kn)≤⌊n/2⌋. Thus π(Kn)=⌊n/2⌋.
(ii)  Assume first thatr=s. Now, if r is odd, then every vertex is of odd degree and hence π(Kr,r)=r. If r is even, then Kr,r can be decomposed into hamiltonian cycles and hence π(Kr,r)≤r/2. Further, for any path decomposition ψ of Kr,r, every member of ψ covers at most 2r edges so that |ψ|≥r2/2r=r/2 and hence π(Kr,r)≥r/2. Thus π(Kr,r)=r/2.
Supposer≠s. If rs is odd, then every vertex is of odd degree and hence π(Kr,s)=(r+s)/2. If rs is even, then π(Kr,s)≤πa(Kr,s)=⌈rs/2r⌉=⌈s/2⌉. Further, for any path decomposition ψ of Kr,s, every member in ψ covers at most 2r edges and hence |ψ|≥⌈rs/2r⌉=⌈s/2⌉. Thus π(Kr,s)=⌈s/2⌉.
(iii)  Since the number of vertices of odd degree inWn is n-1 or n accordingly as n is odd or even, it follows from Theorem 7 that π(Wn)≥⌊n/2⌋. Also by Theorem 1, we have π(Wn)≤⌊n/2⌋ and hence π(Wn)=⌊n/2⌋.We now proceed to obtain some lower and upper bounds forπ involving detour diameter, circumference, and maximum degree of a graph along with the characterization of graphs attaining the bounds.Theorem 11.
For any graphG, π(G)≤m-D+1, where D is the detour diameter of G. Further, equality holds if and only if G is a caterpillar with Δ≤3.Proof.
LetP be a path in G of length D. Then ψ={P}∪{E(G)-E(P)} is a path decomposition of G and |ψ|=m-D+1. Hence, π(G)≤m-D+1.
Supposeπ(G)=m-D+1. Let P be a path of length D in G. If there is a vertex v not on P with degv≥2, let Q be a longest path which contains v and edge-disjoint from P. Thus, ψ={P,Q}∪S, where S is the set of edges not covered by the paths P and Q is a path decomposition of G and |ψ|<m-D+1, which is a contradiction. Thus every vertex not on P is a pendent vertex and hence G is a caterpillar.
Now, if there exists a vertexw on P with degw≥4, let w1 and w2 be two vertices not on P which are adjacent to w. Then ψ1={P,P1=(w1,w,w2)}∪S, where S is the set of edges not covered by the paths P and P1 is a path decomposition of G and |ψ|<m-D+1, which is a contradiction. Hence, degw≤3, for all w∈V(P).
The converse is obvious.Theorem 12.
For any graphG, π(G)≤m-c+1, where c is the circumference of G. Further, equality holds if and only if G is either a cycle or a cycle with exactly one chord or a unicyclic graph with Δ=3 and every vertex not on the cycle is a pendant vertex.Proof.
LetC be a cycle of length c. Then ψ={C}∪{E(G)-E(C)} is a path decomposition of G and |ψ|=m-c+1. Hence π(G)≤m-c+1.
Supposeπ=m-c+1. Let C be a cycle of length c in G. We consider the following two cases.
Case  1  (V(G)=V(C)). We claim that C has at most one chord. Suppose C has two chords say e1 and e2. If e1=vw1 and e2=vw2, then ψ={C,(w1,v,w2)}∪S, where S is the set of edges not covered by C and the path (w1,v,w2) is a path decomposition of G and |ψ|<m-c+1, which is a contradiction. Suppose e1=v1w1 and e2=v2w2. Let P and Q denote the two (v1,v2)-sections of the cycle C and without loss of generality we assume that P contains one of the (w1,w2)-sections of C. Now, let Q1 denote the path consisting of the edge w1v1, followed by the path Q and the edge v2w2. Then ψ1={P,Q1}∪S, where S denotes the set of edges not covered by the paths P and Q1 is a path decomposition of G and |ψ1|<m-c+1, which is a contradiction. Hence, C has at most one chord. Thus G is a cycle or a cycle with exactly one chord.
Case  2  (V(G)≠V(C)). Suppose that there exists a vertex v not on C with degv≥2. Let Q be a longest path which contains v and edge-disjoint from C. Thus ψ={C,Q}∪S, where S is the set of edges not covered by C and Q is a path decomposition of G and |ψ|<m-c+1, which is a contradiction. Thus every vertex not on C is a pendant vertex.
If there exists a vertexv on C with degv≥4, let P be a longest path containing v and edge-disjoint from C. Then ψ={C,P}∪S, where S is the set of edges not covered by C and P is a path decomposition of G with |ψ|<m-c+1, which is a contradiction. Hence every vertex on C has degree less than or equal to 3.
Now, we claim that the cycleC has no chord. Suppose vw is a chord of C. Let y be a pendant vertex not on C. Then there exists a vertex x on C different from the vertices v and w such that x and y are adjacent. Let P and Q denote the two (x,w)-sections of C and without loss of generality we assume that v lies on P. Let Q1 be the path consisting of the edge yx followed by the path Q and the edge wv. Now, ψ={P,Q1}∪S, where S is the set of edges not covered by the paths P and Q1 is a path decomposition of G and |ψ|<m-c+1, which is a contradiction. Hence, C has no chords.
ThusG is a unicyclic graph with Δ=3 and every vertex not on the cycle is a pendant vertex. The converse is obvious.Remark 13.
Obviously, for any vertexv of a graph G, at most two of the edges incident with v can be covered by a member of a path decomposition of G. As this is true in particular for a vertex of maximum degree it follows that π(G)≥⌈Δ/2⌉. This bound is sharp as a complete graph of odd order attains this. In fact, every graph which is hamiltonian cycle decomposable attains the bound. Further, for any tree T, π(T)=⌈Δ/2⌉ if and only if T is homeomorphic to the star K1,Δ.The following theorem characterizes the family of unicyclic graphs achieving the bound given in Remark13.Theorem 14.
LetG be a unicyclic graph with cycle C and G≠C. Then π(G)=⌈Δ/2⌉ if and only if every vertex not on C has degree 1 or 2, at most two vertices on C have degree ≥3 and C has exactly one vertex with degree ≥3 if Δ≥5.Proof.
LetG be a unicyclic graph with π(G)=⌈Δ/2⌉. Let ψ be a minimum path decomposition of G. Let v be a vertex in G with degv=Δ. Then every member of ψ passes through v.
We claim thatv lies on the cycle C. This is obvious if C∈ψ. If C∉ψ, let P1 and P2 be the paths in ψ covering the edges of the cycle C. Since both P1 and P2 pass through v; it follows that v lies on C. Thus every vertex of degree Δ lies on C and consequently every vertex not on C has degree 1 or 2.
Further ifΔ(G)≥5, it follows that G contains exactly one vertex of degree Δ and if Δ(G)≤4, then G contains at most two vertices of degree ≥3.
The converse is obvious.In the following theorem we characterize graphs of ordern with π=⌈Δ/2⌉ and having minimum (maximum) number of edges.Theorem 15.
LetG be a graph of order n with π(G)=⌈Δ/2⌉. Then n-1≤m≤⌈nΔ/2⌉. Further, m=n-1 if and only if  G is homeomorphic to the star K1,Δ. Also m=⌈nΔ/2⌉ if and only if G is hamiltonian cycle decomposable or G is the complete graph Kn with n even.Proof.
LetG be a graph with π(G)=⌈Δ/2⌉. Then G is connected and hence n-1≤m≤⌈nΔ/2⌉.
Now, supposem=n-1. Then G is a tree. As π(G)=⌈Δ/2⌉ it follows that G is homeomorphic to the star K1,Δ. Conversely, if G is homeomorphic to K1,Δ, then π(G)=⌈Δ/2⌉.
Now, supposem=⌈nΔ/2⌉. Then G is Δ-regular. If Δ is even, then for any minimum path decomposition ψ of G, we have |ψ|=Δ/2 and each path in ψ must cover n edges so that G is hamiltonian cycle decomposable. Conversely, if G is hamiltonian cycle decomposable, then π(G)=Δ/2. If Δ is odd, then π(G)=n/2=⌈Δ/2⌉ and hence Δ=n-1. Hence, G=Kn and n is even. The converse follows from Example 10(i).


## 4. Relation between the Parametersπ and πa

In this section we establish some relation between the parametersπ and πa.Theorem 16.
For any graphG, one has π(G)≤πa(G)≤2π(G). Further, πa(G)=2π(G) if and only if every component of G is a cycle.Proof.
The first inequality is already seen. For the other inequality, consider a path decompositionψ of G and spilt each cycle member of ψ into two paths and thus an acyclic path decomposition of G with cardinality at most 2π(G) is obtained, which proves the required inequality. Now suppose πa(G)=2π(G). Let ψ be a minimum path decomposition of G. Then every member of ψ is a cycle. Further, all the cycles in ψ are vertex-disjoint and hence every component of G is a cycle. The converse is obvious.Remark 17.
The first part of the inequalities given in the above theorem is strict in the sense that they both are equal for infinitely many graphs. For example, one has the following.(i)
For even integersn, we have π(Kn)=πa(Kn), which follows from Theorem 5 and Example 10(i).(ii)
Example9 and Theorem 4 together show that the parameters π and πa are equal for all trees and also for the class of all unicyclic graphs other than the cycles.Though the upper bound suggested by Gallai's conjecture forπa and the upper bound given by Theorem 1 for π differ by at most 1, the difference between the actual values of these parameters can be made arbitrarily large, which we proceed to prove. The following lemma is useful in this regard.Lemma 18.
LetG be a connected graph which can be decomposed into a cycle C=(v1,v2,…,vr,v1) and a path P=(w1,…,ws). Then G can be decomposed into two paths if and only if G has a vertex of degree 2 which lies on C or on the (wi1,wi2)-section of P where i1 is the smallest positive integer such that 1≤i1<s and wi1∈V(C) and i2 is the largest positive integer such that i1<i2≤s and wi2∈V(C).Proof.
SupposeG can be decomposed into two paths P1 and P2. Since w1 and ws are the only two vertices of odd degree in G, we may assume that w1 is the origin of P1 and ws is the origin of P2. Let v be the terminus of P1. Since the degree of v is even, it follows that v is not an internal vertex of P2 so that v is the terminus of P2 as well, and the degree of v is 2. Clearly v cannot lie on the (w1,wi1)-section or the (wi2,ws)-section of P.
Conversely, supposeG has a vertex v of degree two satisfying the conditions stated in the lemma. We consider two cases.
Case  1  (v∈V(C)). Since G is connected, |V(P)∩V(C)|≥1. If |V(P)∩V(C)|=1, then trivially G can be decomposed into two paths. Hence, we assume that |V(P)∩V(C)|≥2. If there exists a (v,wi1)-section of C which is internally disjoint from P, let P1 be the path consisting of the (w1,wi1)-section of P followed by the (wi1,v)-section of C which is not internally disjoint from P and let P2 be the path consisting of the (v,wi1)-section of C which is internally disjoint from P followed by the (wi1,ws)-section of P. Then {P1,P2} is a decomposition of G. The proof is similar if there exists a (v,wi2)-section of C which is internally disjoint from P.
Now, suppose both the(v,wi1)-sections of C and both the (v,wi2)-sections of C are not internally disjoint from P. Let r be the largest positive integer such that i1<r<i2 and wr∈V(C). Then the (wr,wi2)-section of P and one of the (wr,wi2)-sections of C, say Q, are internally disjoint. If Q has length greater than 1, then any internal vertex vi of Q has degree 2 and the (vi,wi2)-section of Q is internally disjoint from P and hence the proof is complete. If the (wr,wi2)-section of P has length greater than 1, let P1 be the path consisting of the (ws,wi2)-section of P-1 followed by the (wi2,wr)-section of C which is different from Q followed by the edge wrwr+1 and let P2 be the path consisting of the (wr+1,wi2)-section of P followed by Q-1 followed by (wr,w1)-section of P-1. Then {P1,P2} is a decomposition of G.
Case  2 (no vertex on C has degree 2). In this case v lies on the (wi1,wi2)-section of P. Let v=wi and let a and b be integers with i1≤a<i<b≤i2 such that wa,wb∈V(C) and no internal vertex of the (wa,wb)-section of P lies on C. Without loss of generality we assume that there exists a (wi1,wb)-section of C, say Q1, which contains wa and wi2 and let Q2 be the other (wi1,wb)-section of C. Let P1 be the path consisting of the (w1,wi1)-section of P, followed by Q1 and the (wb,wi)-section of P-1. Let P2 be the path consisting of the (ws,wb)-section of P-1 followed by Q2-1 and the (wi2,wi)-section of P. Then {P1,P2} is a decomposition of G.Corollary 19.
IfG is a graph admitting a minimum path decomposition ψ having exactly one cycle C=(v1,…,vr,v1), then πa≤π+1. Further, πa=π if and only if there exists a path P=(w1,…,ws) in ψ with V(P)∩V(C)≠∅ and the induced subgraph 〈V(C)∪V(P)〉 satisfies the conditions stated in Lemma 18.Theorem 20.
Given any positive integerk, there exists a graph G such that πa(G)-π(G)=k.Proof.
LetG be the graph consisting of k vertex-disjoint cycles C1,C2,…,Ck and  a  u-v  path P=(u,v11,…,v1n1,v21,…,v2n2,…,vk1,vk2,…,vknk,v), where V(Cj)={vj1,vj2,…,vjnj}, for j=1,2,…,k. Clearly π(G)=k+1. Further, πa(G)≤2k+1. We now prove that πa(G)≥2k+1 by induction on k.
Ifk=1, then it follows from Lemma 18 that πa(G)=3=2k+1. Assume that πa(G)≥2r+1, for all graphs G as described above with r<k cycles. Let G be such a graph with k cycles. Let ψ be an acyclic path decomposition of G. Let P1 be the path in ψ containing the edge v1n1v21. Let G1=〈V(C1)∪{u,v21}〉, G2=〈V(C2)∪V(C3)∪⋯∪V(Cn)∪{v,v1n1}〉, H1=G1-E(P1) and H2=G2-E(P1). Let P1′,P2′,…,Pr′ be the paths in ψ which decompose the graph H1 and let P1′′,P2′′,…,Ps′′ be the paths in ψ which decompose the graph H2. Clearly r≥2. We now claim that s≥2k-2. Let w≠v1n1 be the end vertex of P1 which lies in G2. Then the (v1n1,w)-section of P1 together with the paths P1′′,P2′′,…,Ps′′ decompose the graph G2. Hence, by induction hypothesis s+1≥πa(G2)≥2(k-1)+1=2k-1 so that s≥2k-2. Hence, |ψ|=r+s+1≥2+2k-2+1=2k+1 so that πa(G)≥2k+1. Thus πa(G)=2k+1 and so πa(G)-π(G)=k.Theorem 21.
LetG be a connected graph. Then πa(G)=2π(G)-1 if and only if G is the graph consisting of π-1 vertex-disjoint cycles C1,C2,…,Cπ-1 and a path P=(w1,w2,…,wr) satisfying the following conditions.(i)
Every vertex of the cycleCi, 1≤i≤π-1, lies on the path P.(ii)
Ifi1 and i2 denote, respectively, the smallest and the largest positive integer such that wi1,wi2∈V(Ci),1≤i≤π-1, then every edge of the (wi1,wi2)-section of P is a chord of the cycle Ci.Proof.
Supposeπa(G)=2π(G)-1. Let ψ be a minimum path decomposition of G. Then ψ consists of exactly one path, say P and π(G)-1 vertex-disjoint cycles, say C1,C2,…,Cπ(G)-1. Let P=(w1,w2,…,wr). Since G is connected, V(P)∩V(Ci)≠∅ for all i,1≤i≤π(G)-1. Now, if there exists a vertex of degree 2 in G which lies either on any of the cycles Ci or on the (wi1,wi2)-section of P then it follows from Lemma 18 that πa(G)≤2π(G)-2, which is a contradiction. Hence, (i) and (ii) hold.
Now, the graphG given in the theorem is nothing but the graph described in Corollary 19 with k=π-1 and thus the converse follows.Theorem 22.
Given two positive integersa and b with a≤b≤2a, there exists a graph G such that π(G)=a and πa(G)=b.Proof.
Ifb=2a, let G be the graph with a components, each component being a cycle. If b=2a-1, let G be the graph given in Theorem 21. If a=b, let G be the graph consisting of exactly one cut vertex and a blocks, each block being a cycle. In all these cases, π(G)=a and πa(G)=b.
Now, supposea+1≤b≤2a-1. Let b=a+r, where 1≤r≤a-1. Let G be the connected graph consisting of a-1 vertex-disjoint cycles C1,C2,…,Ca-1 and a path P=(w1,w2,…,ws) satisfying the following conditions: (i)
V(P)∩V(Ci)=V(Ci) if 1≤i≤r and V(P)∩V(Ci) is a proper nonempty subset of V(Ci) if r+1≤i≤b;(ii)
ifi1 and i2 denote, respectively, the smallest and largest positive integer such that wi1,wi2∈V(Ci), 1≤i≤r, then each edge of the (wi1,wi2)-section of P is a chord of the cycle Ci.
Clearlyπ(G)=a and it follows from Lemma 18 that πa(G)=2r+1+a-1-r=r+a=b.We conclude the paper by posing the following problem for further researchs.(i)
Characterize graphsG for which π(G)=k/2, where k is the number of vertices of odd degree in G.(ii)
Characterize graphsG for which π(G)=⌊n/2⌋.(iii)
Characterize graphsG for which πa(G)=π.(iv)
Characterize graphs for whichπ(G)=⌈Δ/2⌉.



---

*Source: 721051-2013-04-14.xml*