Special factors,periodicity, and an application to Sturmian words

Let w be a finite word and n the least non-negative integer such that w has no right special factor of length and its right factor of length n is unrepeated. We prove that if all the factors of another word v up to the length n + 1 are also factors of w, thenv itself is a factor ofw. A similar result for ultimately periodic infinite words is established. As a consequence, some ‘uniqueness conditions’ for ultimately periodic words are obtained as well as an upper bound for the rational exponents of the factors of uniformly recurrent non-periodic infinite words. A general formula is derived for the ‘critical exponent’ of a power-free Sturmian word. In particular, we effectively compute the ‘critical exponent’ of any Sturmian sequence whose slope has a periodic development in a continued fraction. Received: 6 May 1999 / 21 February 2000     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

Finding a maximum-density path in a tree under the weight and length constraints

Let T=(V,E) be a tree with n nodes such that each node v is associated with a value-weight pair(valv,wv), where the valuevalv is a real number and the weightwv is a positive integer. The density of a path P=〈v₁,v₂,…,vk〉 is defined as . The weight of P, denoted by w(P), is . Given a tree of n nodes, two integers wmin and wmax, and a length lower bound L, we present a pseudo-polynomial O(wmaxnL)-time algorithm to find a maximum-density path P in T such that wmin?w(P)?wmax and the length of P is at least L.     

Deciding word neighborhood with universal neighborhood automata

Given some form of distance between words, a fundamental operation is to decide whether the distance between two given words w and v is within a given bound. In earlier work, we introduced the concept of a universal Levenshtein automaton for a given distance bound n. This deterministic automaton takes as input a sequence χ of bitvectors computed from w and v. The sequence χ is accepted iff the Levenshtein distance between w and v does not exceed n. The automaton is called universal since the same automaton can be used for arbitrary input words w and v, regardless of the underlying input alphabet. Here, we extend this picture. After introducing a large abstract family of generalized word distances, we exactly characterize those members where word neighborhood can be decided using universal neighborhood automata similar to universal Levenshtein automata. Our theoretical results establish several bridges to the theory of synchronized finite-state transducers and dynamic programming. For small neighborhood bounds, universal neighborhood automata can be held in main memory. This leads to very efficient algorithms for the above decision problem. Evaluation results show that these algorithms are much faster than those based on dynamic programming.     

Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices u,v∈V(G) are joined by a path of length l for all d_G(u,v)?l?|V(G)|-1, where d_G(u,v) is the length of a shortest path joining u and v in G. Recently, Fan et. al. [J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parall. Distrib. Syst. 16 (2) (2005) 1190-1200, J. Fan, X. Jia, X. Lin, Complete path embeddings in crossed cubes, Inform. Sci. 176 (22) (2006) 3332-3346] and Xu et. al. [J.M. Xu, M.J. Ma, M. Lu, Paths in Möbius cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94-97] both proved that n-dimensional crossed cube, CQ_n, is almost panconnected except the path of length d_CQn(u,v)+1 for any two distinct vertices u,v∈V(CQ_n). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length d_CQn(u,v)+1, called the nearly shortest paths, for any two distinct vertices u,v in CQ_n. Moreover, we observe that only some pair of vertices have no nearly shortest path and we give a construction scheme for the nearly shortest path if it exists.     

The twin domination number in generalized de Bruijn digraphs

Let G=(V,A) be a digraph. A set T of vertices of G is a twin dominating set of G if for every vertex v∈V?T, there exist u,w∈T (possibly u=w) such that arcs (u,v),(v,w)∈A. The twin domination numberγ^∗(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we investigate the twin domination number in generalized de Bruijn digraphs GB(n,d). For the digraphs GB(n,d), we first establish sharp bounds on the twin domination number. Secondly, we give the exact values of the twin domination number for several types of GB(n,d) by constructing minimum twin dominating sets in the digraphs. Finally, we present sharp upper bounds for some special generalized de Bruijn digraphs.     

The spanning connectivity of folded hypercubes

A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ_n is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2.     

On a word avoiding near repeats

In this paper we construct an infinite binary word w with the following property: the minimal distance among two occurrences of a same factor of length n cannot be polynomially upperbounded. In particular, for all positive ε the number of distinct factors of w with exponent larger than 1+ε is finite.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

A new sufficient condition for Hamiltonicity of graphs

Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u)+d(v)+δ(u,v)?n+1 for each pair of distinct non-adjacent vertices u and v in G, where δ(u,v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad.     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

Hamiltonian connectivity and globally 3∗-connectivity of dual-cube extensive networks

In 2000, Li et al. introduced dual-cube networks, denoted by DC_n for n?1, using the hypercube family Q_n and showed the vertex symmetry and some fault-tolerant hamiltonian properties of DC_n. In this article, we introduce a new family of interconnection networks called dual-cube extensive networks, denoted by DCEN(G). Given any arbitrary graph G, DCEN(G) is generated from G using the similar structure of DC_n. We show that if G is a nonbipartite and hamiltonian connected graph, then DCEN(G) is hamiltonian connected. In addition, if G has the property that for any two distinct vertices u,v of G, there exist three disjoint paths between u and v such that these three paths span the graph G, then DCEN(G) preserves the same property. Furthermore, we prove that the similar results hold when G is a bipartite graph.     

Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the edges and the vertices. A total coloring is proper if no two adjacent or incident elements receive the same color. An adjacent vertex-distinguishing total coloring h of a simple graph G=(V,E) is a proper total coloring of G such that H(u)≠H(v) for any two adjacent vertices u and v, where H(u)={h(wu)|wu∈E(G)}∪{h(u)} and H(v)={h(xv)|xv∈E(G)}∪{h(v)}. The minimum number of colors required for an adjacent vertex-distinguishing edge coloring (resp. an adjacent vertex-distinguishing total coloring) of G is called the adjacent vertex-distinguishing edge chromatic number (resp. adjacent vertex-distinguishing total chromatic number) of G and denoted by (resp. χat(G)). In this paper, we consider the adjacent vertex-distinguishing edge chromatic number and adjacent vertex-distinguishing total chromatic number of the hypercube Qn, prove that for n?3 and χat(Qn)=Δ(Qn)+2 for n?2.     

On-line maintenance of triconnected components with SPQR-trees

We consider the problem of maintaining on-line the triconnected components of a graphG. Letn be the current number of vertices ofG. We present anO(n)-space data structure that supports insertions of vertices and edges, and queries of the type “Are there three vertex-disjoint paths between verticesv ₁ andv ₂?” A sequence ofk operations takes timeO(k·α(k, n)) ifG is biconnected(α(k, n) denotes the well-known Ackermann's function inverse), and timeO(n logn+k) ifG is not biconnected. Note that the bounds do not depend on the number of edges ofG. We use theSPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and theBC-tree, which represents the decomposition of a connected graph with respect to its biconnected components.     

All-pairs shortest-paths computation in the presence of negative cycles

We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm+n²logn), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance μ(v,w) between each pair v,w of vertices even in the presence of negative cycles, where μ(v,w) is defined as the infimum of the costs of all directed paths from v to w.     

Computing functions on asynchronous anonymous networks

In an “anonymous” network the processors have no identity numbers. We investigate the problem of computing a given functionf on an asynchronous anonymous network in the sense that each processor computesf(I) for any inputI = (I(v ₁),...,I(v _n )), whereI(v _i) is the input to processorv _i ,i = 1, 2,...,n. We address the following three questions: (1) What functions are computable on a given network? (2) Is there a “universal” algorithm which, given any networkG and any functionf computable onG as inputs, computesf onG? (3) How can one find lower bounds on the message complexity of computing various functions on anonymous networks? We give a necessary and sufficient condition for a function to be computable on an asynchronous anonymous network, and present a universal algorithm for computingf(I) on any networkG, which acceptsG andf computable onG, as well as {I(v _i )}, as inputs. The universal algorithm requiresO(mn) messages in the worst case, wheren andm are the numbers of processors and links in the network, respectively. We also propose a method for deriving a lower bound on the number of messages necessary to solve the above problem on asynchronous anonymous networks.     

Vertex vulnerability parameters of Kronecker products of complete graphs

Let G₁ and G₂ be two graphs. The Kronecker product G₁×G₂ of G₁ and G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and edge set and v₁v₂∈E(G₂)}. In this paper, we determine some vertex vulnerability parameters of the Kronecker product of complete graphs Km×Kn for n?m?2 and n?3.     

Ranking numbers of graphs

Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P₂ with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.     

Geodesic pancyclicity and balanced pancyclicity of Augmented cubes

For two distinct vertices u,v∈V(G), a cycle is called geodesic cycle with u and v if a shortest path of G joining u and v lies on the cycle; and a cycle C is called balanced cycle with u and v if dC(u,v)=max{dC(x,y)|x,y∈V(C)}. A graph G is pancyclic [J. Mitchem, E. Schmeichel, Pancyclic and bipancyclic graphs a survey, Graphs and applications (1982) 271-278] if it contains a cycle of every length from 3 to |V(G)| inclusive. A graph G is called geodesic pancyclic [H.C. Chan, J.M. Chang, Y.L. Wang, S.J. Horng, Geodesic-pancyclic graphs, in: Proceedings of the 23rd Workshop on Combinatorial Mathematics and Computation Theory, 2006, pp. 181-187] (respectively, balanced pancyclic) if for each pair of vertices u,v∈V(G), it contains a geodesic cycle (respectively, balanced cycle) of every integer length of l satisfying max{2dG(u,v),3}?l?|V(G)|. Lai et al. [P.L. Lai, J.W. Hsue, J.J.M. Tan, L.H. Hsu, On the panconnected properties of the Augmented cubes, in: Proceedings of the 2004 International Computer Symposium, 2004, pp. 1249-1251] proved that the n-dimensional Augmented cube, AQn, is pancyclic in the sense that a cycle of length l exists, 3?l?|V(AQn)|. In this paper, we study two new pancyclic properties and show that AQn is geodesic pancyclic and balanced pancyclic for n?2.