43:
206:
407:
Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See, for example, Bondy and Murty (1976), Gibbons (1985), or
Diestel (2005).
246:
148:
626:
283:
576:
551:
621:
568:
385:
308:
374:
210:
397:
562:
96:
80:
543:
537:
378:
312:
141:
53:
469:
8:
444:
396:, and in fact the paths are exactly the trees in which no vertex has degree 3 or more. A
393:
389:
339:
263:
255:
65:
20:
464:
111:
19:
This article is about a family of graphs. For paths as parts of arbitrary graphs, see
594:
572:
547:
529:
449:
121:
432:
259:
131:
597:
533:
454:
420:
615:
401:
296:
424:
292:
459:
428:
27:
602:
416:
392:
in that graph. A path is a particularly simple example of a
42:
528:
201:{\displaystyle \{2\cos \left({\frac {k\pi }{n+1}}\right);}
373:. Equivalently, a path with at least two vertices is
213:
151:
592:
240:
200:
560:
613:
388:of other graphs, in which case they are called
381:1), while all others (if any) have degree 2.
235:
152:
571:, vol. 173, Springer-Verlag. pp. 6–9.
384:Paths are often important in their role as
377:and has two terminal vertices (vertices of
499:vertices, some authors (e.g. Diestel) use
423:of type A. As such, they classify the
614:
593:
410:
16:Graph with nodes connected linearly
13:
14:
638:
586:
41:
488:While it is most common to use
241:{\displaystyle k=1,\ldots ,n\}}
539:Graph Theory with Applications
482:
284:Table of graphs and parameters
1:
627:Parametric families of graphs
569:Graduate Texts in Mathematics
475:
419:, path graphs appear as the
7:
438:
315:can be listed in the order
10:
643:
561:Diestel, Reinhard (2005).
542:. North Holland. pp.
47:A path graph on 6 vertices
25:
18:
282:
269:
251:
140:
130:
120:
110:
95:
79:
64:
52:
40:
35:
431:of type A, which is the
26:Not to be confused with
242:
202:
400:of paths is called a
243:
203:
622:Trees (graph theory)
470:Cycle (graph theory)
211:
149:
445:Path (graph theory)
21:Path (graph theory)
595:Weisstein, Eric W.
465:Path decomposition
427:of type A and the
411:As Dynkin diagrams
238:
198:
289:
288:
189:
634:
608:
607:
582:
567:(3rd ed.).
557:
521:
519:
509:
505:
498:
494:
486:
450:Caterpillar tree
372:
361:
337:
278:
247:
245:
244:
239:
207:
205:
204:
199:
194:
190:
188:
177:
169:
122:Chromatic number
106:
91:
75:
60:
45:
33:
32:
642:
641:
637:
636:
635:
633:
632:
631:
612:
611:
589:
579:
554:
534:Murty, U. S. R.
525:
524:
514:
507:
504:
500:
496:
493:
489:
487:
483:
478:
441:
433:symmetric group
421:Dynkin diagrams
413:
363:
360:
349:
343:
335:
329:
322:
316:
277:
273:
262:
260:Bipartite graph
258:
212:
209:
208:
178:
170:
168:
164:
150:
147:
146:
132:Chromatic index
101:
85:
70:
58:
48:
31:
24:
17:
12:
11:
5:
640:
630:
629:
624:
610:
609:
588:
587:External links
585:
584:
583:
577:
558:
552:
523:
522:
506:for a path of
502:
495:for a path of
491:
480:
479:
477:
474:
473:
472:
467:
462:
457:
455:Complete graph
452:
447:
440:
437:
412:
409:
398:disjoint union
355:
347:
338:such that the
333:
327:
320:
287:
286:
280:
279:
275:
271:
267:
266:
253:
249:
248:
237:
234:
231:
228:
225:
222:
219:
216:
197:
193:
187:
184:
181:
176:
173:
167:
163:
160:
157:
154:
144:
138:
137:
134:
128:
127:
124:
118:
117:
114:
108:
107:
99:
93:
92:
83:
77:
76:
68:
62:
61:
56:
50:
49:
46:
38:
37:
15:
9:
6:
4:
3:
2:
639:
628:
625:
623:
620:
619:
617:
605:
604:
599:
596:
591:
590:
580:
578:3-540-26182-6
574:
570:
566:
565:
559:
555:
553:0-444-19451-7
549:
545:
541:
540:
535:
531:
527:
526:
517:
512:
485:
481:
471:
468:
466:
463:
461:
458:
456:
453:
451:
448:
446:
443:
442:
436:
434:
430:
426:
422:
418:
408:
405:
403:
402:linear forest
399:
395:
391:
387:
382:
380:
376:
370:
367:= 1, 2, ...,
366:
358:
354:
350:
341:
336:
326:
319:
314:
310:
306:
302:
298:
294:
285:
281:
272:
268:
265:
261:
257:
256:Unit distance
254:
250:
232:
229:
226:
223:
220:
217:
214:
195:
191:
185:
182:
179:
174:
171:
165:
161:
158:
155:
145:
143:
139:
135:
133:
129:
125:
123:
119:
115:
113:
112:Automorphisms
109:
104:
100:
98:
94:
89:
84:
82:
78:
73:
69:
67:
63:
57:
55:
51:
44:
39:
34:
29:
22:
601:
598:"Path Graph"
564:Graph Theory
563:
538:
530:Bondy, J. A.
515:
510:
484:
414:
406:
383:
368:
364:
356:
352:
345:
331:
324:
317:
305:linear graph
304:
300:
297:graph theory
293:mathematical
290:
102:
87:
71:
425:root system
616:Categories
476:References
460:Null graph
429:Weyl group
301:path graph
252:Properties
36:Path graph
28:line graph
603:MathWorld
520:vertices.
386:subgraphs
375:connected
295:field of
227:…
175:π
162:
536:(1976).
439:See also
362:} where
313:vertices
270:Notation
142:Spectrum
97:Diameter
54:Vertices
417:algebra
330:, ...,
307:) is a
291:In the
575:
550:
379:degree
311:whose
81:Radius
544:12–21
511:edges
390:paths
340:edges
309:graph
66:Edges
573:ISBN
548:ISBN
513:and
394:tree
342:are
303:(or
299:, a
264:Tree
415:In
371:− 1
159:cos
105:− 1
90:/2⌋
74:− 1
618::
600:.
546:.
532:;
518:+1
435:.
404:.
359:+1
351:,
323:,
606:.
581:.
556:.
516:n
508:n
503:n
501:P
497:n
492:n
490:P
369:n
365:i
357:i
353:v
348:i
346:v
344:{
334:n
332:v
328:2
325:v
321:1
318:v
276:n
274:P
236:}
233:n
230:,
224:,
221:1
218:=
215:k
196:;
192:)
186:1
183:+
180:n
172:k
166:(
156:2
153:{
136:2
126:2
116:2
103:n
88:n
86:⌊
72:n
59:n
30:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
