Transcription
Stanford Department of Computer ScienceReport No. STAN-CS-80-807PATH-REGULAR GRAPHSDavid W. MatulaDanny DolevResearch sponsored byNational Science FoundationandOffice of Naval ResearchCOMPUTER SCIENCE DEPARTMENTStanford University'June1980
Path-Regular GraphsDavid W. Matula Iand Danny Dolev**Computer Science DepartmentStanford UniversityStanford, California 94305June 1930Abstract:A graph is vertex-[edge-Ipath-regular if a list of shortestpaths, allowing multiple copies of paths, exists where every pair ofvertices are the endvertices of the same number of paths and each vertex[edge] occurs in the same number of paths of the list.The dependenciesand independencies between the various path-regularity, regularity ofdegree, and symmetry properties are investigated. We show that everyconnected vertex-[edge-Isymmetric graph is vertex-[edge-Ipath-regular,but not conversely.We show that the product of any two vertex-path-regular graphs is vertex-path-regular but not conversely, and the iteratedproduct GxGx. xG is edge-path-regular if and only if G isedge-path-regular.An interpretation of path-regular graphs is givenregarding the efficient design of concurrent communication networks.Keywords:concurrent network flow, product graphs, regularity,shortest paths, symmetry.*JThis research was supported in part by National Science FoundationMCS-77-23738 and by Office of Naval Research contract NOOO14-76-C-033( I.Reproduction in whole or in part is permitted for any purpose of theUnited States government.**/This research was supported in part by a Chaim Weizmann PostdoctoralFellowship.t/ On sabbatical leave from Department of Computer Science/Engineering,Southern Methodist University, Dallas, Texas 75275.1
I.Introduction and Summary.A combinatorial regularity property of a graph is expressed by anumerical requirement on the consistency of structure TcJithin the graph.The standard property that a graph is regular of degree k , requiringsimply that each vertex be adjacent to exactly k other vertices, hasreceived the most thorough investigation in the literature.The morestringent conditions of "strongly regular" [ C78] and "distance-regular"[B74] have also received considerable treatment. In this paper wecharacterize and investigate the regularity of connectivity that canexist between NWall pairs of vertices concurrently.This regularity isrealized by the identification of equitable numbers of shortest pathsbetween all pairs of vertices that at the same time make equitable useof either each vertex, each edge, or both.To develop the concept ofpath-regularity we explicitly specify our terminology for describingshortest paths in a graph.Other graph theoretic terms not defined heremay be found in Harary [H@].For n - 0, the sequence vo,vl).,vnof distinct vertices of thegraph G , where vivi l is an edge of G for all 0 5 i n-l , shalldenote a path of length n .and vnJv. . .,von-l'Paths are assumed unordered, so vo,v19., vndenote the same path. Vertices v. and vn areendvertices of the path vo,v19.,vn , with all other vertices of thepath then being interior vertices. The path v3,vl,.,vn is a shortestpath of G whenever any other path with endvertices v. and vn haslength at least"0and vn'n , with d(vo,vn) nthen denoting the -distance- - betweenAll paths of length at least one have a distinct pair of2
endvertices.The path v.of length zero has the single endvertexand is also said to have the nondistinct pairvo' "0v. 'of endvertices.Hence a connected graph may be taken to contain shortest paths betweenevery (unordered distinct or nondistinct) pair of vertices.For the complete bipartite graph K15 of Figure l(a), every pairof vertices are the endvertices of a unique shortest path.A list ofall the resulting shortest paths would then have each edge, but not eachvertex, occur in the same number(5)of paths of the list, providing aconcept of regularity for the shortest paths versus the edges ofThe list of all shortest paths for the cycleC5 15lof Figure l(b) wo;rldthen have each vertex occur in the same number (6) of shortest pathsand each edge occur in the same number(3) of shortest paths, yieldinga stronger concept of regularity encompassing the shortest paths, vertices,and edges ofc5If we allow multiple copies of shortest paths of thelx Kp of Figure l(c) in composing a path list, then it is3where each pairpossible to exhibit a list of shortest paths of%x%of vertices v,v' E V(? x , are the endvertices of the same number ofgraphshortest paths of the list and where each vertex, but not each edge, isin the same number of shortest paths of the list.This then providesa concept of regularity for shortest paths versus vertices of3Formally, let a list (equivalently multiset) denote a finitexK2 .collection of elements where multiple copies of each element may occurin the list.A nontrivial graph G is termed vertex-path-regular[respectively, edge-path-regular] with parameters (k,mv) [respectively(k,me) ] if an associated list x of shortest paths of G exists whereevery pair of vertices are the endvertices of exactly k 1 paths of e3
(4Figure 1.Examples of (a) edge-path-regular,wstrongly path-regular, andcc vertex-path-regular graphs.4
and each vertex [respectively, edge] occurs in exactly mvme ] paths of 1: .[respectively,A graph is strongly path-regular with parametersand associated list 1: of shortest paths if it is bothov pe)vertex-path-regular with parametersparameters(k, m.Jand edge-path-regular with(k,me) for the same associated list . For completenessthe trivial graph is taken to be vertex-, edge-, and strongly path-regularwith parametersk l.(k,k) , (k,k) and (k,k,k) , respectively, for everyA graph is said to be vertex-, edge-, or strongly path-regularwhenever there exist some parameters for which the graph has thespecified path-regularity property, and a graph is said to be path-regularif it is at least either vertex- or edge-path-regular.From our preceeding discussion it is then clear thatFigure l(a) is edge-path-regular with parameters%5 Of(L5) t and C5 ofFigure l(b) is strongly path-regular with parameters(l&,3) . Forof Figure l(c), consider the list 1: containing two copies of3xsevery shortest path of length at most one inand one copy ofSx every shortest path of length two. By direct application of the definitionthis list 1: is then sufficient to confirm thatregular with parametersc&14)5x%is vertex-path-lNote that if G is vertex- or edge-path-regular with parametersbqorowe) 9 respectively, or strongly path-regular with parameters(k,mv9me) , then the associated list must have each vertex ofG presentas a path of length zero with multiplicity k and each adjacent p&r ofvertices of G present as a path of length one with multiplicity k .Thus it is sufficient to show that each edge occurs in exactly (me-k)paths of length 2 2 of the list to confirm the edge-path-regularity
property, and/or that each vertex occurs as an interior vertex inexactly mv -k\V(G)\paths of the list to confirm the vertex-pathConsider the wheelregularity property."15of Figure 2.Giving2 to the shortest paths of length two with interiormultiplicityvertexWand multiplicity1 to the other shortest paths of lengthtwo, we note that each edge then appears in the same nwnber (2) ofthese paths. HenceW5is edge-path-regular with parametersAlternatively, giving multiplicityand multiplicityus to confirm thatThe graph W5(4,Ql1 to the same paths containing vl2 to the other shortest paths of length two allowsW5(5,271is vertex-path-regular with parameterslis not regular (of degree), so by Theorem 1 of the nextsection can not be strongly path-regular.Hence the example W3demonstrates that a graph can be both vertex-path-regular and edge-pathregular without being strongly path-regular.Path-regular graphs may be visualized as providing efficient designof communications networks,graph with parametersowe)Let the vertices of an edge-path-regularrepresent communication bases in thenetwork and the edges trunk lines each cap*able of hosting meof concurrent communication.channelsThe edge-path-regularity property thenallows for k dedicated communication channels to be provided betweenevery pair of bases concurrently.Furthermore, the channel allocationis efficient both in that all dedicated channels follow shortest pathsand that every trunk line is used to full capacity.If the constraintin a communication network is alternatively related to a fixed level ofswitching capacity at every communication base, then the vertex-pathregular graphs indicate efficient network design.The associated lists
“sFigure 2.The wheel W5with parameterswith parameterspath-regular.which is vertex-path-regular(5927) and edge-path-regular(4,6) , yet not strongly
of the path-regular graphs, as specified for the examples of Figures 1and 2, then provide the dedicated channels for such a communicationnetwork interpretation.This concurrent communication interpretationprovides some motivation and an intuitive appeal to many of ourderived results but is not explicitly mentioned in the balance of thepaper.The example graphs of Figures 1 and 2 all possessed considerablesymmetry that was instrumental in the demonstration of the respectivepath-regularity properties of these graphs.in his book Algebraic Graph TheoryAs succinctly noted by Biggs[B74], "A symmetry property of a graphis related to the existence of automorphisms -- that is, permutations ofthe vertices which preserve adjacency.in purely numerical terms.A regularity property is definedConsequently, symmetry properties induceregularity properties, but the converse is not necessarily true."In Section II we investigate the dependencies and independenciesbetween the various regularity, path-regularity, and symmetry properties.Cur main result is in accord with the preceeding observation on regularityand symmetry properties.wSpecifically, we show that:*a connected vertex-symmetric f graph is vertex-path-regular butnot conversely,**(ii)a connectededge-symmetric -f graph is edge-path-regular but notconversely, and(iii)a connected graph that is both vertex- and edge-synmetric isstrongly path-regular but not conversely.*J Also termed vertex-transitive by some authors.**-.IAlso termed edge-transitive by some authors,
These results insure that many important classes of graphs have aCycles, cubes and regular cmplete k-partitepath-regularity property.graphs are strongly path-regular, and any complete bipartite graph isedge-path-regular.We also indicate in Section II the considerableextent to which the vertex-, edge-, and strongly path-regular propertiesare independent of other graph properties and parameter values.The fact that a graph is vertex- or edge-path-regular does notdetermine the parameters(k,mv)or(k,m,)uniquely, but it uniquelydetermines their ratio. Hence we define a(G) k/mv as the vertexpath-regularity of the vertex-path-regular graph G and p(G) k/m,as the edge-path-regularity of the edge-path-regular graph G . InSection III we obtain the following formulas for evaluating a(G) andp(G) :For any vertex-path-regular graph G with n vertices and 1 edges,nco(G)xv,v' U(G)Cd(v,v' llfor 2; of any diameter, nfor G of diameter 2,2-n-21i 3nG with n vertices and 1 l edges,and for any edge-path-regular graph-afor G of any diametercd(v, v' v,v' eV(G)p(G) an(ii-TyjTif G has diameter - 2 .I9
A table of values of a(G) and p(G)classes of path-regular graphs.is then provided for the majorIn Section III we also derive somenontrivial necessary conditions for a graph to be vertex- and/oredge-path-regular involving inequalities between the relative sizeof the cuts and separating sets of the graph and the required valuesfor c andp from the preceeding formulas.There is an intimate relation between shortest paths in the product graphThis relation is exploited inGxH and the shortest paths of G and H .Section IV to obtain our major results on the products of path-regular graphs:(i) The producty graph GxH is vertex-path-regular whenever G andH are both vertex-path-regular, but not conversely, and(ii) the product graph GxH is edge-path-regular if and only if Gand H are both edge-path-regular withIV(G) \p@ IV(H) Ip@) twhere specifically Gx GX . . . xG is edge-path-regular if andonly if G is edge-path-regular.Finally, in Section V, we propose and discuss several interestingopen questions that arose in our investigation of path-regular graphs,of which the most intriguing to us is the following:edge-path-regular graphG with p(G) rIs there anfor every nonzero rational rin the unit interval?*JAlso termed the Cartesian product graph,in Section IV.10The product graph is defined
II.Rwularity, Path-Regularity and Symmetry.The primary goal of this section is to determine the dependenciesand independencies between the various regularity, path-regularity, andOur first theorem provides some affirmativesymmetry properties.implications between regularity (of degree) and path-regularityproperties.of Figure 2 illustrates that aAlthough the wheel W5graph can be vertex-path-regular and/or edge-path-regular withoutbeing regular, Theorem 1 demonstrates that a strongly path-regulargraph must be regular. And conversely, although the property that theconnected graph G be regular of degreek is not by itself sufficientto induce either the vertex- or edge-path-regularity property for G ,the property that the connected graph G be strongly regular issufficient to *make G strongly path-regular.whenever G is regular of degree il ,* ,i.j 12regular with parametersNote that G is strongly-where also any two adjacent vertices have exactlyand any two nonadjacent vertices have exactlyTheorem 1.i3common neighbors,i2common neighbors.A strongly path-regular graph with parametersand n vertices is regular of degree (2mv-kn-k)/m, .hand, any strongly regular graph with parametersProof.3’mv 3rd(k,mv' ,!ni il(il-i2-1)/2 , and me i 2(il-i2-1)33Let the n vertex graphparameters (k,mv9me) , wherespecific vertex vOn the other(i 1, i2, i3 2 1)n 2 vertices is strongly path-regular with parameterswhere k i(kG pe)lG be strongly path-regular withJ is the associated list of paths, Anyof G will occur as an endvertex in k(n-1) pathsof length at least one in1: , and each of these paths will containll
exactly one edge incident to v .vertex inAlso, vwill occur as an interiormv-kn paths of J , where each of these paths will containexactly two edges incident to v .of edges incident to vThus the total nurriber of occurencesin all paths of 1: is 2mv-kn-k .But thetotal number of occurences of edges incident to v in all paths of d:is also given by mexdegree(v) since each edge of G occurs in mepaths of 1: . Therefore degree(v) ( Smv-kn-k)/m, for any v in G .For the second part of the theorem let the graph G (V,E) haven 2vertices and be strongly regular with parametersLet the list e containVEV 9i3i3copies of the pathof the path u,v, wand every distinctcopies of the zero length path v for everyv, w for each edge V-WEE , and one copyfor every nonadjacent pair of distinct vertices u,weVv adjacent to both u and w .every two nonadjacent vertices ofthat e contains k ivertices of G .(il,i2,i3 1) .G haveiThe fact thatcommon neighbors implies3 l shortest paths between every pair of3-Any edge V-WEE occurs ini3paths of length oneNoting that there areil-i2-1 vertices other than v adjacentto w and not to v and alsoil-i2-1 vertices other than w adjacentof x.to v and not to w , the edgeVWalso occurs in 2(il-i2-1) of thepaths of length two of J, so in total in me i3 2(il-i2-1) pathsof 1:.Every vertexVeV Will Occur as an endvertex inni3 pathsof 1: and as the mid-vertex of il(il-i2-1)/2 paths of length two of 6: ,so in total inni il(il-i2-1)/2 paths of 1 .3path-regular with the associated list I: . 1312Hence G is strongly
As another partial converse to the first part of Theorem 1 we nowderive the following lemma which will be employed in the subsequenttheorem.Lemma 2.Every graph which is both regular and edge-path-regular isstrongly path-regular.Proof.Let the n vertex graph G be regular of degree j andedge-path-regular with parameterslist of paths.1: is the associatedFor any vertex v of G , there are jme occurencesof edges incident tothe jme(k,me) , wherev in the paths of x .A total of k(n-1) ofsuch occurences correspond to v being an en&vertex, thev being an interior vertex of the paths.remainder corresponding toEach occurence of v as an interior vertex of a path involves exactlytwo occurences of edges incident to v in that path, so v must occuras an interior vertex in[jm e-k(n-1)]/2vertex v of G occurs inpaths of 1: . Hence each[jm, k(n-1)]/2 paths of J , so G isstrongly path-regular with paraketers(k, be kb-1) l/&me) .c7As previously noted, the sylnnetrie s characterized by the automorphismsof a graph induce extensive numerical regularity properties, although theconverse implications generally do not hold.In accord with this maxim,the standard vertex and edge spmetry properties of graphs are now shownto induce the corresponding vertex- and edge-path-regularity propertieswhile the converses are shown to fail by counterexamples.13
Theorem3.wEvery connected vertex-symmetric graph is vertex-path-regular, butnot conversely;every connected edge-symmetric graph is edge-path regular, but not(ii)conversely;(iii)every connected graph that is both vertex- and edge-symmetric isstrongly path-regular.However, there exist strongly path-regulargraphs that are, respectively, not vertex-symmetric and notedge-symmetric.Proof.Let G (V,E)edge-symmetric or both.b e connected and either vertex-symmetric orLet k(u,v) be the number of distinct shortestpaths between u and v in G , and let k* lcm{k(u,v) \ u,vev} .Let the list 1 containbetween u and vk*/k(u, v for all pairs of vertices of V , so then every pa.iru,veV are the endvertices of k*Assumecopies of each distinct shortest pathpaths of g .G is vertex-symmetric. For each veV , form the sublist .&composed of all paths of d: containing the vertex v .the assumption thatautomorphism cxG is vertex-symmetric means there exists anmapping vmapped by Q! to a path,into u .Now any path p of xv isa(p) J containing the vertex uis also a shortest path between its endvertices inin e, .For any v,ueV ,where4P)G ) so Cl(p)isFurthermore, each distinct shortest path between the endverticesof the path p is mapped by a into a distinct shortest path betweenthe endvertices of the path a(p) and vice-versa for the inverseautomorphism Q!-1.Thus p has the same multiplicity in14d:Va.5a(P)
L,(,Ll INow assumesublistX,lSince CX-1is an automorphism mappingand G is vertex-path-regular verifying (i).G is edge-symmetric and for each edge eeE form thecomposed of all paths of J containing the edge e .any two edgesFore,e' EE ) the assumption that G is edge-symmetric meansthere exists an automorphism a which maps edge e into edge e' .By the same argument as preceeding we then obtain thatfor any edges e,e' eE , soI’el I’ef IG is edge-path-regular verifying (ii).Noting that the same list 2 was utilized in the proofs of both (9and (ii) then verifies (iii).To show none of the converses hold first consider the wheelof Figure 2.w5is neither vertex- nor edge-symmetric, yet it isboth vertex- and edge-path-regular, demonstrating that neither theconverse of (i) nor (ii) hold.For counterexamples to the converse of (iii) first note thatFolkman [F67; 78, p. 951 has demonstrated the existence of a regulargraph which is edge-symmetric but not vertex-symmetric.By part (ii)of this theorem and Lemma 2 such a graph is then strongly path-regularwithout being vertex-symmetric,To demonstrate that a strongly path-regular graph need not be edge-symmetric, consider the graphC C5 5composed of two distinct chordless five cycles along with all edgesbetween vertices of these distinct five cycles.each path of GThe list containingof length zero or one with multiplicity7 , each pathof length two in a chordless five cycle having multiplicity 2 , andeach path of length two with nonadjacent endvertices in one chordlessfive cycle and midvertex in the other five cycle having multiplicity 1 ,15
is sufficient to confirm thatpara;neters(7,77,11) .C C5 5is strongly path-regular withAlthough C5 C5is clearly vertex-symmetric,it is not edge-symmetric since some edges are in chordless five cyclesand others are not, completing the theorem. 0From Theorem3 it follows that the class of strongly path-regulargraphs is quite broad, including all cycles, complete graphs, regularcomplete k-partite graphs, and the cubes of every dimension,all ccmplete bipartite graphs are edge-path-regular.AlsoAs might beexpected, the condition that a graph be vertex-, edge-, or stronglypath-regular is quite independent of most other typical parameter valuesand/or properties associated with a graph, a partial summary of which isnoted in the following.Corollary 3.1.There exist strongly path-regular graphs of any specifiedgirth, or of any specified diameter, or of any specified edge or vertexconnectivity,Proof.diameteror of any specified chromatic number.The cycle Cnis strongly path-regular of girth nandLGJ , thus realizing any specified girth or diameter,The complete graph Kn l , regular complete bipartite graphKn n ,Yand n dimensional cube are all examples of strongly path-regulargraphs of edge and vertex connectivity n .The complete graph Knand any regular complete n-partite graph have chromatic number n .16g
Two properties of a graph will be termed independent propertiesif there are examples of graphs exhibiting all four possible cases:(a) having both properties,without the other, and(b) having each specified property(c) having neither property.Figure3 providesexamples showing that the property that a regular graph be stronglypath-regular is independent of the property that a graph be either(i) Hamiltonian, or (ii) Eulerian,that the graphs of Figureor (iii) planar. Verification3 satisfy the respective properties isstraightforward from standard results in the literature regarding theseproperties.To confirm that the cited example graphs are not stronglypath-regular, consider the following:Every edge of an n vertex graph,other than Kn , that is edge-path-regular with parameters (k,me) musthave each edge occur inassociated list.Observation.me-k - 1 paths of length at least two in theAlternatively:If G is a graph other than a complete graph where someedge of G does not occur in any shortest path between any nonadjacentendvertices in G , then G is not edge-path-regular, hence also notstrongly path-regular.17
I4IIIIHamiltonianPlanarINot HamiltonianEulerianNot EulerianNot Planar!I1!iiItRegular andStronglyPath-Regular,Regular andNot StronglyPath-RegularFigure3.Graphs showing that the property that a connected regulargraph be strongly path-regular is indenpendent of theproperties that a graph be either (i) Hamiltonian, or(ii) Eulerian, or (iii) planar.Now let us return to the primary theine of this section which is todescribe the dependencies and independencies that exist between the variousregularity, path-regularity, and symmetry properties.In Figure 4 andthe following corollaries we describe the extent to which the vertex-pathregularity and edge-path-regularity properties are distinct and independent ofother regularity and symmetry properties,.18
INot ularandregd-arNot regular‘1I( s Not vertex-symmetricEdge-symmetricl(3 edge-path-regular)0Not edge-path-regular(* Not edge-symmetric)----Figure 4.An indication of the independence of regularity,path-regularity, and symmetry properties.Corollary 3.2.The property that a graph be edge-path-regularindependent of the property that a graph beor (ii)Proof.vertex-path-re,gular, or (iii)(i)isvertex-symmetric,re,gAar.All possible cases are covered by the examples of Figure 4.Three of the four example graphs are immediately seen to have theindicated properties.The other graph,3x%.,is the classic exampleof a graph that is vertex- but not edge-symmetric, and we need only showthat it is not edge-path-regular.From the theorems proved in Section IVit follows that Kix K. is vertex symmetric but not edge-path-regularJfor any i j 2. We include a separate proof for %x to keepthis section self-contained.19
Let the six edges of5x%edges and the other three be typepath of length two inSOy-2that are in triangles be type ABedges.uses one typeNote that every shortestA and one type B edge,any list of shortest paths in which every pair of vertices of%xK2are the endvertices of the same number of shortest paths can not haveeach edge occur in the same nwnber of paths.Corollary 3.3.0The property that a graph be vertex-path-regular isindependent of the property that a graph be (i) edge-symmetric, or(ii) edge-path-regular, or (iii) regular.Proof.Figure 4.All cases for (i) and (ii) are confirmed by the examples ofTo show that the property of being vertex-path-regular isindependent of the property of being regular, note thatK2has bothproperties, Klhas neither property, and the wheel W5 of Figure 2Y2is vertex-path-regular but not regular. Finally the regular graph ofFigure 3 (lower right corner) that is Eulerian and not planar and notstrongly path-regular is readily seen not to be vertex-path-regularas the separating vertex would have to be an interior vertex of toomany paths. c120
III. kraluation of Path-Regularity.Although knowledge that a graph G is either vertex- or edge-path-regularis not sufficient to determine the parameters(k,m) Y it is now shown tobe sufficient to determine their ratio k/m .The class of vertex- andedge-path-regular grapns of diameter two are of special importance andthe ratio k/m takes on a particularly simple formulation in that case.Theorem 4.Let G be a vertex-path-re,tiar'where G has vertex setregularityc VlYV2Yl ll ,7Jn 3and 1 edges.0% "JThe vertex-path-c(G) is then given bynfIof any diameter,for GIO(G)graph with parameters(1)C Cd(Vi,Vj ) lJi ,i ” V2nfor G of diameter 2,23n -n-21whereProof.(2)d(vi,vj) denotes the distance between vi and v. .JLet G be a vertex-path-regular graph with parametersand associated list e of shortest paths.in all paths of x is given by0% "JThe total number of verticesk C Cd(vi,vj) ‘Isince each pairi jof vertices v. , v. are the endvertices of k paths of length d(vi,vj)13where each such path contains d(vi,vj) l vertices. But the totalnumber of vertices in all paths of 1: is also given by nm Veach vertex occurs inmv paths of 1: . Thusk [d(Vi,Vj ) ‘I nmv ,i jverifying formula (1).21since
When G has diameter at most two,1: must then contain exactlykn paths of length zero, k1 paths of length one, with the remainingk[n(n-1)/2 - 11 paths of length two, yielding formula (2). [7An analogous result is now stated for edge-path-regular graphs,where the proof is immediate by the same arguments utilized in thepreceedingTheorem 5.theorem.Let Gbe an edge-path-regular graph with parameterswhere G has vertex setedge-path-regularity[v ,v ,.,v,)1 2P(G)and R l- edges.owe)Theis then given by&for G of any diameter,(3)for G of diameter - 2 .(4)' d(Vi,Vj i jp(G) ” eRn(n-l)-lFran (1) and (3) we then obtain:Corollary 5.1.For any strongly path-regular era-oh with n verticesand 0 - 1 edges,nqq- &1- 2 ri(n l) .P(G)(5)Formulas (l)-(4) allow for straightforward computation ofand p(G)a(G)when G is known to be vertex- and/or edge-path-regular.Complete graphs, cycles, regular complete j -partite graphs, and thecubes of all dimensions a.we known to be strongly path-regular from theresults of Section II, and the values of (522andp for these graphs
.1 edge-path-regularityPvertex-path-regularityClasses of Graphs0Complete: Kn1';;188Pn even, n 4----Tb 2 n2Cycle: Cn8--n odd, n 2 38(n 2)2-ln2-1Regular Completej-partite:ji-iji i-2K. . .1,1,.,1j -dimension Cube:12j-12.t.J(j P)Pj-' lNot edge-path-regularProduct ofjij-F-j 1KixK.JComplete Graphs:for i j 2Not vertex-path-Complete Bi-partite:K.1 3regular foriji2 if3j2 ij-i-1Table 1.Values of the vertex-path-regularity and edge-pathregularity for several important classes of path-regulargraphs.23j
are tabulated in Table 1.The product graph KixK. is vertex symmetric,Jhence vertex-path-regular. The value of 0 for KixK. along with theJvalue of p for the edge-path-regular complete bipartite graph K.1, jare also given in Table 1.The relation between c and p given by (5)is seen to hold for the four classes of strongly path-regular graphs inThe fact that Kix K. is not edge-path-regular for i jz23follows from Theorem 3 of Section IV. It is also noted in Table 1 thatTable 1.is not vertex-path-regular for ifj. For this fact considerK.b 3that in any list having the same number of shortest paths between allK.for i j , the number of times a vertex1, joccurs as an interior vertex of a path of the list is greater for verticespairs of vertices ofof the jmembered set than for the imembered set.Utilization of formulas (1) - (4) as in Table 1 req-.Cres that wefirst know that the graphs have the corresponding path-regularity property.A test to determine if a particular graph is vertex- and/or edge-pathregular can be developed utilizing the computationalprogramming.procedure of linearSuch a test to determine if a graph is edge-path-regularis outlined in the following.A Test for Edge-Path-Regularity of G.IJet p CPl,P2'"" pj]graph G .wAssign nonnegative weights xi to the paths of P such that:the sum of the weights xiendvertices(ii)be the set of all shortest paths of thefor all paths of P between thev,v' eV(G) is unity for every pairv,v' O(G) ,the sum of the weights on the paths containing the edgeis less than or equal to zfor every eeE(G) , and24e E E(G)
(iii) zminis the minimum value of zof (i), (ii), wherezminbe found efficiently by linearFrom Theorem 5 we then obtain:programming techniques.(a) if fmincansatisfying the constraintsb(G) 1, then G is not edge-path-xdbb v' v,v' O(G)regular,
Note that if G is vertex- or edge-path-regular with parameters bq or owe) 9 respectively, or strongly path-regular with parameters (k,mv9me) , then the associated list must have each vertex of G present as a path of length zero with multiplicity k and each adjacent p&r of vertices of G present as a path of length one with multiplicity k .
