In 1969, Lovász asked if every finite, connected vertex-transitive graph has a Hamilton path. In spite of its easy formulation, no major breakthrough has been achieved thus far, and the problem is now commonly accepted to be very hard. The same holds for the special subclass of Cayley graphs where the existence of Hamilton cycles has been conjectured. In 2007, Glover and Marušič proved that a cubic Cayley graph on a finite $(2, s, 3)$-generated group $G = \langle a, x| a^2 = x^s = (ax)^3 = 1, \dots \rangle$ has a Hamilton path when $|G|$ is congruent to 0 modulo 4, and has a Hamilton cycle when $|G|$ is congruent to 2 modulo 4. The Hamilton cycle was constructed, combining the theory of Cayley maps with classical results on cyclic stability in cubic graphs, as the contractible boundary of a tree of faces in the corresponding Cayley map. With a generalization of these methods, Glover, Kutnar and Marušič in 2009 resolved the case when, apart from $|G|$, also $s$ is congruent to 0 modulo 4. In this article, with a further extension of the above "tree of faces" approach, a Hamilton cycle is shown to exist whenever $|G|$ is congruent to 0 modulo 4 and s is odd. This leaves $|G|$ congruent to 0 modulo 4 with s congruent to 2 modulo 4 as the only remaining open case. In this last case, however, the "tree of faces" approach cannot be applied, and so entirely different techniques will have to be introduced if one is to complete the proof of the existence of Hamilton cycles in cubic Cayley graphs arising from finite $(2, s, 3)$-generated groups.
COBISS.SI-ID: 1024390740
In the paper we show that the bibliographic data can be transformed into a collection of compatible networks. Using network multiplication different interesting derived networks can be obtained. In defining them an appropriate normalization should be considered. The proposed approach can be applied also to other collections of compatible networks. The networks obtained from the bibliographic data bases can be large (hundreds of thousands of vertices). Fortunately they are sparse and can be still processed relatively fast. We answer the question when the multiplication of sparse networks preserves sparseness. The proposed approaches are illustrated with analyses of collection of networks on the topic "social network" obtained from the Web of Science. The works with large number of co-authors add large complete subgraphs to standard collaboration network thus bluring the collaboration structure. We show that using an appropriate normalization their effect can be neutralized. Among other, we propose a measure of collaborativness of authors with respect to a given bibliography and show how to compute the network of citations between authors and identify citation communities.
COBISS.SI-ID: 16739929
The Jahn-Teller (JT) theorem predicts spontaneous symmetry breaking and lifting of degeneracy in degenerate electronic states of (nonlinear) molecular and solid-state systems. In these cases, degeneracy is lifted by geometric distortion. Molecular problems are often modelled using spectral theory for weighted graphs, and the present paper turns this process around and reformulates the JT theorem for general vertex- and edge-weighted graphs themselves. If the eigenvectors and eigenvalues of a general graph are considered as orbitals and energy levels (respectively) to be occupied by electrons, then degeneracy of states can be resolved by a non-totally symmetric re-weighting of edges and, where necessary, vertices. This leads to the conjecture that whenever the spectrum of a graph contains a set of bonding or anti-bonding degenerate eigenvalues, the roots of the Hamiltonian matrix over this set will show a linear dependence on edge distortions, which has the effect of lifting the degeneracy. When the degenerate level is non-bonding, distortions of vertex weights have to be included to obtain a full resolution of the eigenspace of the degeneracy. Explicit treatments are given for examples of the octahedral graph, where the degeneracy to be lifted is forced by symmetry, and the phenalenyl graph, where the degeneracy is accidental in terms of the automorphism group.
COBISS.SI-ID: 16090457
Sierpiński graphs $S_p^n$ form an extensively studied family of graphs of fractal nature applicable in topology, mathematics of the Tower of Hanoi, computer science, and elsewhere. An almost-extreme vertex of $S_p^n$ is introduced as a vertex that is either adjacent to an extreme vertex of $S_p^n$ or is incident to an edge between two subgraphs of $S_p^{n}$ isomorphic to $S_p^{n-1}$. Explicit formulas are given for the distance in $S_p^{n}$ between an arbitrary vertex and an almost-extreme vertex. The formulas are applied to compute the total distance of almost-extreme vertices and to obtain the metric dimension of Sierpiński graphs.
COBISS.SI-ID: 16582233
A graph X is said to be G-half-arc-transitive if G⩽Aut(X) acts transitively on the set of vertices of X and on the set of edges of X but does not act transitively on the set of arcs of X. Such graphs can be studied via corresponding alternets, that is, equivalence classes of the so-called reachability relation, first introduced by Cameron, Praeger and Wormald (1993). If the vertex sets of two adjacent alternets either coincide or have half of their vertices in common the graph is said to be tightly attached. In this paper graphs admitting a half-arc-transitive group action with at most five alternets are considered. In particular, it is shown that if the number of alternets is at most three, then the graph is necessarily tightly attached, but there exist graphs with four and graphs with five alternets which are not tightly attached. The exceptional graphs all admit a partition giving the rose window graph R6(5,4)R6(5,4) on 12 vertices as a quotient graph in case of four alternets, and a particular graph on 20 vertices in the case of five alternets.
COBISS.SI-ID: 1536241092