Cycle embedding in star graphs with conditional edge faults

Among the various interconnection networks, the star graph has been an attractive one. In this paper, we consider the cycle embedding problem in star graphs with conditional edge faults. We show that there exist cycles of all even lengths from 6 to n! in an n-dimensional star graph with ?2n-7 edge faults in which each vertex is incident with at least two healthy edges for n?4.     

Embedding cycles of various lengths into star graphs with both edge and vertex faults

The n-dimensional star graph S_n is an attractive alternative to the hypercube graph and is a bipartite graph with two partite sets of equal size. Let F_v and F_e be the sets of faulty vertices and faulty edges of S_n, respectively. We prove that S_n − F_v − F_e contains a fault-free cycle of every even length from 6 to n! − 2∣F_v∣ with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4. We also show that S_n − F_v − F_e contains a fault-free path of length n! − 2∣F_v∣ − 1 (respectively, n! − 2∣F_v∣ − 2) between two arbitrary vertices of S_n in different partite sets (respectively, the same partite set) with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4.     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.     

VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS

In this paper, we study the enhanced hypercube, an attractive variant of the hypercube and obtained by adding some complementary edges from a hypercube, and focus on cycles embedding on the enhanced hypercube with faulty vertices. Let Fu be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k （n ≥ 3, 1 ≤ k 〈≤n - 1）. When IFvl = 2, we showed that Qn,k - Fv contains a fault-free cycle of every even length from 4 to 2n - 4 where n （n ≥ 3） and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n - 4, simultaneously, contains a cycle of every odd length from n-k ＋ 2 to 2^n-3 where n （≥ 3） and k have the different parity. Furthermore, when ｜Fv｜ = fv ≤ n - 2, we prove that there exists the longest fault-free cycle, which is of even length 2^n - 2fv whether n （n ≥ 3） and k have the same parity or not; and there exists the longest fault-free cycle, which is of odd length 2^n - 2fv ＋ 1 in Qn,k - Fv where n （≥ 3） and k have the different parity.     

Edge-bipancyclicity of a hypercube with faulty vertices and edges

A bipartite graph G=(V,E) is said to be bipancyclic if it contains a cycle of every even length from 4 to |V|. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F_v (respectively, F_e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_n. In this paper, we show that every edge of Q_n-F_v-F_e lies on a cycle of every even length from 4 to 2ⁿ-2|F_v| even if |F_v|+|F_e|?n-2, where n?3. Since Q_n is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

Embedding long cycles in faulty k-ary 2-cubes

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. Given an even k ? 4, let (V₁, V₂) be the bipartition of the k-ary 2-cube, f_v1, f_v2 be the numbers of faulty vertices in V₁ and V₂, respectively, and f_e be the number of faulty edges. In this paper, we prove that there exists a cycle of length k² − 2max{f_v1, f_v2} in the k-ary 2-cube with 0 ? f_v1 + f_v2 + f_e ? 2. This result is optimal with respect to the number of faults tolerated.     

On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks

It is shown in this work that all n-dimensional hypercube networks for n ? 4 are maximally 3-restricted edge connected. Employing this observation, we analyze the reliability of hypercube networks and determine the first 3n − 5 coefficients of the reliability polynomial of n-cube networks.     

Small subgraphs in random graphs and the power of multiple choices

The standard paradigm for online power of two choices problems in random graphs is the Achlioptas process. Here we consider the following natural generalization: Starting with G₀ as the empty graph on n vertices, in every step a set of r edges is drawn uniformly at random from all edges that have not been drawn in previous steps. From these, one edge has to be selected, and the remaining r−1 edges are discarded. Thus after N steps, we have seen rN edges, and selected exactly N out of these to create a graph GN.In a recent paper by Krivelevich, Loh, and Sudakov (2009) [11], the problem of avoiding a copy of some fixed graph F in GN for as long as possible is considered, and a threshold result is derived for some special cases. Moreover, the authors conjecture a general threshold formula for arbitrary graphs F. In this work we disprove this conjecture and give the complete solution of the problem by deriving explicit threshold functions N₀(F,r,n) for arbitrary graphs F and any fixed integer r. That is, we propose an edge selection strategy that a.a.s. (asymptotically almost surely, i.e. with probability 1−o(1) as n→∞) avoids creating a copy of F for as long as N=o(N₀), and prove that any online strategy will a.a.s. create such a copy once N=ω(N₀).     

星图的条件容错哈密尔顿性

证明了在任意n（≥5）维星图中去掉2n-9条边且使得去边后的图的每个点关联至少两条边,得到的图是边-哈密尔顿的.     

Estimation of flows in flow networks

Let G be a directed graph with an unknown flow on each edge such that the following flow conservation constraint is maintained: except for sources and sinks, the sum of flows into a node equals the sum of flows going out of a node. Given a noisy measurement of the flow on each edge, the problem we address, which we call the Most Probable Flow Estimation problem (MPFE), is to estimate the most probable assignment of flow for every edge such that the flow conservation constraint is maintained. We provide an algorithm called ΔY-mpfe for solving the MPFE problem when the measurement error is Gaussian (Gaussian-MPFE). The algorithm works in O(∣E∣ + ∣V∣²) when the underlying undirected graph of G is a 2-connected planar graph, and in O(∣E∣ + ∣V∣) when it is a 2-connected serial-parallel graph or a tree. This result is applicable to any Minimum Cost Flow problem for which the cost function is τ_e(X_e − μ_e)² for edge e where μ_e and τ_e are constants, and X_e is the flow on edge e. We show that for all topologies, the Gaussian-MPFE’s precision for each edge is analogous to the equivalent resistance measured in series to this edge in an electrical network built by replacing every edge with a resistor reflecting the measurement’s precision on that edge.     

On bipartite graphs with minimal energy

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. In a paper [G. Caporossi, D. Cvetkovi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996] Caporossi et al. conjectured that among all connected graphs G with n≥6 vertices and n−1≤m≤2(n−2) edges, the graphs with minimum energy are the star S_n with m−n+1 additional edges all connected to the same vertices for m≤n+⌊(n−7)/2⌋, and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. The conjecture is proved to be true for m=n−1,2(n−2) in the same paper by Caporossi et al. themselves, and for m=n by Hou in [Y. Hou, Unicyclic graphs with minimal energy, J. Math. Chem. 29 (2001) 163-168]. In this paper, we give a complete solution for the second part of the conjecture on bipartite graphs. Moreover, we determine the graph with the second-minimal energy in all connected bipartite graphs with n vertices and edges.     

Broadcasting with random faults

We consider the problem of broadcasting in an n-vertex graph a message that originates from a given vertex, in the presence of random edge faults. If the number of edge faults is at most proportional to the total number of edges, there are networks for which the broadcast can be done in time O(log n), with high probability.     

A bound on the total size of a cut cover

A cycle cover (cut cover) of a graph G is a collection of cycles (cuts) of G that covers every edge of G at least once. The total size of a cycle cover (cut cover) is the sum of the number of edges of the cycles (cuts) in the cover.We discuss several results for cycle covers and the corresponding results for cut covers. Our main result is that every connected graph on n vertices and e edges has a cut cover of total size at most 2e-n+1 with equality precisely when every block of the graph is an odd cycle or a complete graph (other than K₄ or K₈). This corresponds to the result of Fan [J. Combin. Theory Ser. B 74 (1998) 353-367] that every graph without cut-edges has a cycle cover of total size at most e+n-1.     

Counting substructures I: Color critical graphs

Let F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits (1968) [8], who proved that there is one copy of F, and of Rademacher, Erd?s (1962) [1] and [2] and Lovász and Simonovits (1983) [4], who proved similar counting results when F is a complete graph.One of the simplest cases of our theorem is the following new result. There is an absolute positive constant c such that if n is sufficiently large and 1?q<cn, then every n vertex graph with ⌊n²/4⌋+q edges contains at least

     

Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

Bounding the gap between extremal Laplacian eigenvalues of graphs

Let G be a graph whose Laplacian eigenvalues are 0 = λ₁ ? λ₂ ? ? ? λ_n. We investigate the gap (expressed either as a difference or as a ratio) between the extremal non-trivial Laplacian eigenvalues of a connected graph (that is λ_n and λ₂). This gap is closely related to the average density of cuts in a graph. We focus here on the problem of bounding the gap from below.