N1-0011 — Annual report 2011
1.
Isomorphism checking of I-graphs

We consider the class of ▫$I$▫-graphs, which is a generalization of the class of the generalized Petersen graphs. We show that two ▫$I$▫-graphs ▫$I(n, j, k)$▫ and ▫$I(n, j_1, k_1)$▫ are isomorphic if and only if there exists an integer ▫$a$▫ relatively prime to $n$ such that either ▫$\{j_1, k_1\} = \{aj \mod n, \; ak \mod n \}$▫ or ▫$\{j_1, k_1\} = \{aj \mod n, \; -ak \mod n\}$▫. This result has an application in the enumeration of non-isomorphic ▫$I$▫-graphs and unit-distance representations of generalized Petersen graphs.

COBISS.SI-ID: 16069977
2.
Visual analysis of large graphs using (X,Y)-clustering and hybrid visualizations

Many different approaches have been proposed for the challenging problem of visually analyzing large networks. Clustering is one of the most promising. In this paper, we propose a new clustering technique whose goal is that of producing both intracluster graphs and intercluster graph with desired topological properties. We formalize this concept in the ▫$(X,Y)$▫-clustering framework, where ▫$Y$▫ is the class that defines the desired topological properties of intracluster graphs and ▫$X$▫ is the class that defines the desired topological properties of the intercluster graph. By exploiting this approach, hybrid visualization tools can effectively combine different node-link and matrix-based representations, allowing users to interactively explore the graph by expansion/contraction of clusters without loosing their mental map. As a proof of concept, we describe the system Visual Hybrid ▫$(X,Y)$▫-clustering (VHYXY) that implements our approach and we present the results of case studies to the visual analysis of social networks.

COBISS.SI-ID: 16097881
3.
On dihedrants admitting arc-regular group actions

In the paper, the authors prove the following theorem. Let Γ be a connected Cayley graph of a dihedral group D2n admitting an arc-regular action of a subgroup D2n≤G≤Aut(Γ) such that every cyclic subgroup of index 2 in D2n is core-free in G. Then Γ is isomorphic to the lexicographic product of the tensor product Kn1⊗⋯⊗Knt by Kcm, where 2n=mn1⋯nt with n1,…,nt pairwise coprime. As the authors point out, this theorem gives only a possible structure for such a Cayley graph Γ. The only known examples are K4, K4[Kc2], and Kn,n=K2[Kcn]. Finally, some applications of the main theorem are given.eorem are given.

COBISS.SI-ID: 102427707