Some families of combination and permutation graphs. (Q2829062)

The authors use definitions of \textit{S. M. Hegde} and \textit{S. Shetty} [Appl. Math. E-Notes 6, 251--258 (2006; Zbl 1194.05139)], which they formulate as follows. Let \(G\) be a graph with \(n\) vertices with an injection \(f\) from the vertices of \(G\) to \(\{1,\dots,n\}\). Then \(G\) is a permutation graph if \(f\) is such that the induced edge function \(g_f\) defined as \(g_f(uv)=f(u)!/|f(u)-f(v)|!\) is injective. And \(G\) is a combination graph if \(f\) is such that the induced edge function \(g_f\) defined as \(g_f(uv)=f(u)!/|f(u)-f(v)|!f(v)!\) is injective.NEWLINENEWLINECombination graphs are:NEWLINE\begin{itemize}NEWLINE\item the dragon \(D_{n,m}\) for every \(n\), \(m\), which is the graph obtained from the cycle \(C_n\) by joining the end point of a path \(P_m\) to one vertex of \(C_n\);NEWLINE\item the triangular snake \(T_n\), \(n\ge 3\), which is the graph obtained from the path \(P_n\) with the vertices \(v_1,\dots,v_n\) by adding new vertices \(w_1,\dots,w_{n-1}\) and connecting \(w_i\) to the vertices \(v_i,v_{i+1}\) for each \(i\);NEWLINE\item the \(k\)-crown \(kC_n\), \(n\ge 3\), the graph obtained by adding \(k\) pendant edges to every vertex in the cycle \(C_n\) for certain \(k\).NEWLINE\end{itemize}NEWLINENEWLINEPermutation graphs are:NEWLINE\begin{itemize}NEWLINE\item the wheels \(W_n=C_n+K_1\) for \(n>3\);NEWLINE\item the fans \(F_n=P_n+K_1\);NEWLINE\item the triangular snakes \(T_n\) for every \(n\).NEWLINE\end{itemize}