0
$\begingroup$

While going through the Introductory chapter of 'Graph Theory' by Bondy and Murty, I came across the definition of 'path' that says it's a sequence of vertices in such a way that two vertices are adjacent if they are consecutive in the sequence and non-adjacent otherwise.

However, on different sources I read that a path is just a sequence of vertices in such a way that two vertices are adjacent if consecutive and no vertex is repeated in the sequence.

I'm having trouble solving questions that involve the application of path. Kindly guide me through the correct definition of 'path' and why the definition is different in a standard text such as Bondy and Murty ?

$\endgroup$
3
  • $\begingroup$ Let me see if I understand this correctly. The way I read your paraphrase of the definition in Bondy and Murty, there is no path longer than two vertices in any complete graph $K_n$ where $n \geq 3$. Is that right? $\endgroup$
    – Brian Tung
    Commented Sep 1, 2015 at 21:22
  • $\begingroup$ @BrianTung You can probably infer this from the definition of Bondy and Murty. Kindly refer to Page 4, last paragraph in the link bayanbox.ir/view/5987091202670485677/… $\endgroup$ Commented Sep 1, 2015 at 21:33
  • $\begingroup$ Some authors will specify a simple path to mean that vertices never repeat along the path. When the problem under discussion is a shortest path (and edges are counted as positive length), then it follows that such shortest paths are inevitably simple, and no special qualification is necessary. $\endgroup$
    – hardmath
    Commented Sep 2, 2015 at 2:18

2 Answers 2

3
$\begingroup$

The word path is often used in two different contexts:

  1. A path graph is a graph consisting of a sequence of vertices such that two vertices are adjacent in the graph if and only if they are consecutive in the sequence. The notation $P_n$ is often used for a path graph of length $n$. This is what Bondy & Murty describe.

  2. A path in a graph is a subgraph of a given graph that is isomorphic to a path graph. In other words, one might say there is a path in $G$ of length $n$, and by this we mean $P_n$ is a subgraph of $G$.

The word 'path' is used in both ways, but it's usually clear from context what is meant.

$\endgroup$
2
$\begingroup$

Ahh, I think Bondy and Murty mean adjacent in the path if they are consecutive in the sequence, and non-adjacent otherwise. It's just their way of saying no vertex is repeated; if no vertex is repeated, then two vertices are adjacent in the sequence iff they are consecutive in the sequence. Conversely, if two vertices manage to be adjacent in a sequence without being consecutive in the sequence, that can only be because a vertex was repeated. (E.g., in the sequence $(a, b, c, d, b, e)$, the second and fourth elements are adjacent, despite being non-consecutive, only because $b$ is repeated.)

Frankly, I find the no-vertex-repeated statement more intuitive, but the definitions are identical.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .