Open AccessFast Recognition of Some Parametric Graph Families
Author(s) -
Nina Klobas,
Matjaž Krnc
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.18690/978-961-286-516-0.7
Subject(s) - computer science , modular decomposition , parametric statistics , theoretical computer science , combinatorics , pathwidth , symmetric graph , algorithm , graph , discrete mathematics , mathematics , line graph , voltage graph , statistics
Recognizing graphs with high level of symmetries is hard in general, and usually requires additional structural understanding. In this paper we study a particular graph parameter and motivate its usage by devising eÿcient recognition algorithm for the family of I-graphs. For integers m a simple graph is cycle regular if every path of length ` belongs to exactly cycles of length m. We identify all cycle regular I-graphs and, as a conse-quence, describe linear recognition algorithm for the observed family. Similar procedure can be used to devise the recog-nition algorithms for Double generalized Petersen graphs and folded cubes. Besides that, we believe the structural observations and methods used in the paper are of independent interest and could be used for solving other algorithmic problems.