On the notion of infinite Hamiltonian graph

Based on the terms “end” and “cofinal spanning subtree” a general notion of Hamiltonicity of infinite graphs is developed. It is shown that the cube of every connected locally finite graph is Hamiltonian in this generalized sense.     

On the Laplacian spectrum of an infinite graph

In this paper, we introduce the notion of Laplacian spectrum of an infinite countable graph in a different way than in the papers by B. Mohar. We prove some basic properties of this type of spectrum. The approach used is in line with our approach to the limiting spectrum of an infinite graph. The technique of the Laplacian spectrum of finite graphs is essential in this approach.     

Extremal infinite graph theory

We survey various aspects of infinite extremal graph theory and prove several new results. The lead role play the parameters connectivity and degree. This includes the end degree. Many open problems are suggested.     

On a class of packet-switching networks on an infinite graph

A class of open queueing networks with packet switching is discussed. The configuration graph of the network may be finite or infinite. The external messages are divided into standard pieces (packets) each of which is transmitted as a single message. The messages are addressed, as a rule, to nearest neighbours and thereby the network may be treated as a small perturbation of the collection of isolated servers. The switching rule adopted admits overtaking: packets which appeared later may reach the delivery node earlier. The transmission of a message is completed when its last packet reaches the destination node. The main result of this paper is that the network possesses a unique stationary working regime. Weak dependence properties of this regime are established as well as the continuity with respect to the parameters of the external message flows.     

On the combinatorial structure of Rauzy graphs

Let S _m ⁰ be the set of all irreducible permutations of the numbers {1, ??,m} (m ?? 3). We define Rauzy induction mappings a and b acting on the set S _m ⁰ . For a permutation ?? ?? S _m ⁰ , denote by R(??) the orbit of the permutation ?? under the mappings a and b. This orbit can be endowed with the structure of an oriented graph according to the action of the mappings a and b on this set: the edges of this graph belong to one of the two types, a or b. We say that the graph R(??) is a tree composed of cycles if any simple cycle in this graph consists of edges of the same type. An equivalent formulation of this condition is as follows: a dual graph R*(??) of R(??) is a tree. The main result of the paper is as follows: if the graph R(??) of a permutation ?? ?? S _m ⁰ is a tree composed of cycles, then the set R(??) contains a permutation ?? ₀: i ? m + 1 ? i, i = 1, ??,m. The converse result is also proved: the graph R(?? ₀) is a tree composed of cycles; in this case, the structure of the graph is explicitly described.     

On the limit of large girth graph sequences

Let d≥2 be given and let μ be an involution-invariant probability measure on the space of trees T ∈ T _d with maximum degrees at most d. Then μ arises as the local limit of some sequence {G _n } _n=1^∞ of graphs with all degrees at most d. This answers Question 3.3 of Bollobás and Riordan [4].     

The spectrum of an infinite graph

The spectrum of a locally finite countable graph is defined. Some theorems known from the theory of spectra of finite graphs are extended to infinite graphs.     

Factorizations of infinite sequences in semigroups

It follows from the Ramsey theorem that every infinite sequence of elements of a finite semigroup has an infinite factorization of the form x, e, e, e, ..., where e is an idempotent of the semigroup. We describe all semigroups with this property and with its analog for two-sided infinite sequences.     

Weighted automata and weighted logics on infinite words

We introduce weighted automata over infinite words with Muller acceptance condition and we show that their behaviors coincide with the semantics of weighted restricted MSO-sentences. Furthermore, we establish an equivalence property of weighted Muller and weighted Büchi automata over certain semirings.     

Reconstructing the number of copies of a valency-labeled finite graph in an infinite graph

Suppose that G, H are infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such that G - ξ ? H - Ψ(ξ) for every ξ ～ V(G). Let J be a finite graph and /(π) be a cardinal number for each π ? V(J). Suppose also that either /(π) is infinite for every π ? V(J) or J has a connected subgraph C such that /(π) is finite for every π ? V(C) and every vertex in V(J)/V(C) is adjacent to a vertex of C. Let (J, I, G) be the set of those subgraphs of G that are isomorphic to J under isomorphisms that map each vertex π of J to a vertex whose valency in G is /(π). We prove that the sets (J, I, G), m(J, I, H) have the same cardinality and include equal numbers of induced subgraphs of G, H respectively.     

Spectral graph features for the classification of graphs and graph sequences

In this paper, the classification power of the eigenvalues of six graph-associated matrices is investigated. Each matrix contains a certain type of geometric/ spatial information, which may be important for the classification process. The performances of the different feature types is evaluated on two data sets: first a benchmark data set for optical character recognition, where the extracted eigenvalues were utilized as feature vectors for multi-class classification using support vector machines. Classification results are presented for all six feature types, as well as for classifier combinations at decision level. For the decision level combination, probabilistic output support vector machines have been applied, with a performance up to 92.4 %. To investigate the power of the spectra for time dependent tasks, too, a second data set was investigated, consisting of human activities in video streams. To model the time dependency, hidden Markov models were utilized and the classification rate reached 98.3 %.     

Dissipative sequences in infinite ergodic theory

Let T be an invertible, ergodic, measure-preserving transformation on a nonatomic, infinite, σ-finite measure space . A set is weakly wandering under the sequence of integers W={n_i}_i=1^∞ if the sets T^n_iA are disjoint. If, for a given sequence W, there exists a weakly wandering set of positive measure, then we call W a weakly wandering sequence. A sequence {k_i}_i=1^∞ is dissipative if, for every function , we have , almost everywhere. Every weakly wandering sequence is dissipative. In 1978, Hajian and Ito constructed a dissipative sequence which is not weakly wandering. An example of a dissipative sequence which is not a finite union of weakly wandering sequences is presented. Also, some further properties of dissipative sequences are studied.     

Everywhere -repetitive sequences and Sturmian words

Local constraints on an infinite sequence that imply global regularity are of general interest in combinatorics on words. We consider this topic by studying everywhere α-repetitive sequences. Such a sequence is defined by the property that there exists an integer N≥2 such that every length-N factor has a repetition of order α as a prefix. If each repetition is of order strictly larger than α, then the sequence is called everywhere α⁺-repetitive. In both cases, the number of distinct minimal α-repetitions (or α⁺-repetitions) occurring in the sequence is finite.A natural question regarding global regularity is to determine the least number, denoted by M(α), of distinct minimalα-repetitions such that an α-repetitive sequence is not necessarily ultimately periodic. We call the everywhere α-repetitive sequences witnessing this property optimal. In this paper, we study optimal 2-repetitive sequences and optimal 2⁺-repetitive sequences, and show that Sturmian words belong to both classes. We also give a characterization of 2-repetitive sequences and solve the values of M(α) for 1≤α≤15/7.     

Construction of infinite unimodular sequences with zero autocorrelation

Unimodular waveforms x are constructed on the integers with the property that the autocorrelation of x is one at the origin and zero elsewhere. There are three different constructions: exponentials of the form e^{2 pi na q},e^{2 pi i n^alpha theta}, sequences taken from roots of unity, and sequences constructed from the elements of real Hadamard matrices. The first is expected and elementary and the second is based on the construction of Wiener. The third is the most intricate and is really one of a family of distinct but structurally similar waveforms. A natural error estimate problem is posed for the last construction. The analytic solution is not as useful as the simulations because of the inherent counting problems in the construction.