2
$\begingroup$

I have copied a section from Bondy's Graph theory book:

image from book

The idea is to count the mappings between two simple graphs $G$ and $H$ on the same vertex set $V$ according to the intersection of the image of $G$ with $H$. Each such mapping is determined by a permutation $\sigma$ of $V$, which one extends to $G=(V,E)$ by setting $\sigma(G):=(V,\sigma(E))$, where $\sigma(E):=\{\sigma(u)\sigma(v):uv\in E\}$. For each spanning subgraph $F$ of $G$, we consider the permutations of $G$ which map the edges of $F$ onto edges of $H$ and the remaining edges of $G$ onto edges of $\bar H$. We denote their number by $|G\to H|_F$, that is: $$|G\to H|_F:=|\{\sigma\in S_n:\sigma(G)\cap H=\sigma(F)\}|$$

I personally deciphered the notation |G->H|F as no. of distinct mapping of edges from a spanning subgraph F of G to H and the remaining edges (edges of G - edges of F) being mapped to H' taken together. In short it would be most helpful if someone could explain what |G → H|F notation means, would be most helpful with a simple example graph. And sorry if it is a trivial question because I am new to graph theory and the biggest problem that I mostly face is understanding what a theorem means because of the extensive use of mathematical symbols and notations and I mostly interpret wrong or miss out something.

$\endgroup$

2 Answers 2

4
$\begingroup$

Subscript $F$.
$G$ and $H$ are two graphs on the same vertex set.
$F$ s a subgraph of $G$.
This notation is defined in the link.
$$ |\;G\rightarrow H\;|_F $$ is the number of permutaitons of $G$ that map the edges of $F$ onto edges of $H$, and the rest of the edges of $G$ onto $\overline{H}$. I guess $\overline{H}$ is the complement of $H$ (on the same vertex set).

$\endgroup$
1
  • $\begingroup$ I saw it but had trouble to understand 'the number of permutaitons of G that map the edges of F onto edges of H. For ex if we have a graph with 4 vertices a,b,c,d and edge set G is {(a,b),(b,c),(c,d),(d,a)} and F a subgraph of G with edge set {(a,b)} and H with {(a,b),(b,c),(c,a),(b,d)}. How would the mapping look like? $\endgroup$
    – Nilu45
    Commented Jun 9, 2023 at 16:57
2
$\begingroup$

Suppose we have $4$ vertices; $G$ is a cycle (left) and $H$ is a path (right):

1--2    1--2
|  |       |
|  |       |
4--3    4--3

Imagine the vertices $1, 2, 3, 4$ as being in fixed locations. We first swap the vertices of $G$ around according to some permutation, and then we lay the result on top of $H$ and see how many edges match up. If $\sigma$ is the permutation $(2\;3)$ that swaps vertices $2$ and $3$ (but keeps $1$ and $4$ fixed), then the edges $\{12, 23, 34, 14\}$ of $G$ become $\{13, 32, 43, 14\}$ when we apply $\sigma$. Equivalently, the edges of $\sigma(G)$ are $\{13, 23, 34, 14\}$ (because order of endpoints doesn't matter). In a picture, here is how $\sigma(G)$ (left) compares to $H$ (middle):

1  2    1--2    1  2
|\/|       |       |
|/\|       |       |
4  3    4--3    4  3

Only one of the edges matches up: the edge $23$. So the graph $F$ consisting of their intersection is the graph above on the right: the graph with one edge $23$ and two isolated vertices.

In our example, the cycle graph $G$ has many automorphisms. For example, the permutation $(1\;2)\;(3\;4)$ which swaps vertices $1$ and $2$ and also swaps vertices $3$ and $4$ leaves $G$ unchanged (we take the square and reflect it horizontally, and we get back an identical square). So in fact, there are only three possible values of $\sigma(G)$, each one obtained by $8$ of the $24$ permutations of the vertex set:

1  2    1--2    1--2
|\/|     \/     |  |
|/\|     /\     |  |
4  3    4--3    4--3

Their intersections with $H$ are:

1  2    1--2    1--2
   |               |       
   |               |       
4  3    4--3    4--3

Call these graphs $F_1$, $F_2$, and $F_3$ from left to right. ($F_1$ is a graph with a single edge $23$; $F_2$ is a graph with two edges $12$ and $34$; $F_3$ is $H$ itself.)

Because each of these results corresponds to $8$ permutations, we get $$|G \to H|_{F_1} = |G \to H|_{F_2} = |G \to H|_{F_3} = 8.$$ For every other possible graph $F$, we have $|G \to H|_F = 0$.

$\endgroup$
2
  • $\begingroup$ Crystal clear thank you very much.. $\endgroup$
    – Nilu45
    Commented Jun 9, 2023 at 18:23
  • $\begingroup$ This really helped. So as far as I understood there are surely 24 permutations of C4 out of which distinct are only 3 .Each 3 has eight instances each which when intersected with example H gives us still 3 distinct graphs one H itself of f1,f2,f3 Obviously and trivially we get eight instances of f1,f2 and f3 because it is derived from 3 distinct permutation of C4 but |G->H|F=8 bcoz each f1, f2,f3 is repeated eight times Also if we intersect it with f4 doesn't belong to f1,f2,f3 then |G->H|F4=0 bcoz no intersection yields F4. Hence, the last result. $\endgroup$
    – Nilu45
    Commented Jun 9, 2023 at 18:33

You must log in to answer this question.

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