Some families of combination and permutation graphs.
type: Item
instance of: scholarly article
zbMATH Open document ID: 1474.05342
publication date: 2016-10-26T00:00:00Z
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 6644254
zbMATH Keywords: permutation graph
zbMATH Keywords: combination graph
zbMATH Keywords: wheel
zbMATH Keywords: fan
zbMATH Keywords: snake
MaRDI profile type: Publication
Recommended article: Q5505216
Recommended article: On permutation graphs
Recommended article: On combination and permutation graphs
Recommended article: Connected permutation graphs
Recommended article: Permutation graphs and the weak Bruhat order
Recommended article: Q3183088
Recommended article: Q5411933
Recommended article: Q3826572
Recommended article: Q4820824
Recommended article: Generalized Petersen graphs which are cycle permutation graphs
author: M. A. Seoud
author: M. Anwar
title: Some families of combination and permutation graphs.
published in: Ars Combinatoria
review text: 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}
reviewed by: Ulrich Knauer
description: scientific article; zbMATH DE number 6644254