BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
This paper gives an approximate result related to Seymour's Second Neighborhood conjecture, that is, for any m-free digraph G, there exists a vertex v∈V(G) and a real number λm such that d++(v)≥λmd+(v), and λm→1 while m→+∞. This result generalizes and improves some known results in a sense.
Fault tolerance of an (n,k)-star network is measured by its h-super connectivity κs(h) or h-super edge-connectivity λs(h). Li {\it et al.} [Appl. Math. Comput. 248 (2014), 525-530; Math. Sci. Lett. 1 (2012), 133-138] determined κs(h) and λs(h) for 0≤h≤n−k. This paper determines κs(h)=λs(h)=(n−k)!(h+1)!(n−h−1) for n−k≤h≤n−2.
This paper considers the edge-connectivity and restricted edge-connectivity of replacement product graphs, gives some bounds on edge-connectivity and restricted edge-connectivity of replacement product graphs and determines the exact values for some special graphs. In particular, the authors further confirm that under certain conditions, the replacement product of two Cayley graphs is also a Cayley graph, and give a necessary and sufficient condition for such Cayley graphs to have maximum restricted edge-connectivity. Based on these results, the authors construct a Cayley graph with degree d whose restricted edge-connectivity is equal to d+s for given odd integer d and integer s with d⩾5 and 1⩽s⩽d−3, which answers a problem proposed ten years ago.
For an interconnection network G, the {\it ω-wide diameter} dω(G) is the least ℓ such that any two vertices are joined by ω internally-disjoint paths of length at most ℓ, and the {\it (ω−1)-fault diameter} Dω(G) is the maximum diameter of a subgraph obtained by deleting fewer than ω vertices of G. The enhanced hypercube Qn,k is a variant of the well-known hypercube. Yang, Chang, Pai, and Chan gave an upper bound for dn+1(Qn,k) and Dn+1(Qn,k) and posed the problem of finding the wide diameters and fault diameters of Qn,k. By constructing internally disjoint paths between any two vertices in the enhanced hypercube, for n≥3 and 2≤k≤n we prove Dω(Qn,k)=dω(Qn,k)={d(Qn,k)d(Qn,k)+1for 1≤ω<n−⌊2k⌋;for n−⌊2k⌋≤ω≤n+1. where d(Qn,k) is the diameter of Qn,k. These results mean that interconnection networks modelled by enhanced hypercubes are extremely robust.
Let Gn be an n-dimensional recursive network. The h-embedded connectivity ζh(Gn) (resp. edge-connectivity ηh(Gn)) of Gn is the minimum number of vertices (resp. edges) whose removal results in disconnected and each vertex is contained in an h-dimensional subnetwork Gh. This paper determines ζh and ηh for the hypercube Qn and the star graph Sn, and η3 for the bubble-sort network Bn.
The conditional diagnosability and the 2-extra connectivity are two important parameters to measure ability of diagnosing faulty processors and fault-tolerance in a multiprocessor system. The conditional diagnosability tc(G) of G is the maximum number t for which G is conditionally t-diagnosable under the comparison model, while the 2-extra connectivity κ2(G) of a graph G is the minimum number k for which there is a vertex-cut F with ∣F∣=k such that every component of G−F has at least 3 vertices. A quite natural problem is what is the relationship between the maximum and the minimum problem? This paper partially answer this problem by proving tc(G)=κ2(G) for a regular graph G with some acceptable conditions. As applications, the conditional diagnosability and the 2-extra connectivity are determined for some well-known classes of vertex-transitive graphs, including, star graphs, (n,k)-star graphs, alternating group networks, (n,k)-arrangement graphs, alternating group graphs, Cayley graphs obtained from transposition generating trees, bubble-sort graphs, k-ary n-cube networks and dual-cubes. Furthermore, many known results about these networks are obtained directly.
The pebbling number of a graph G, f(G), is the least p such that, however p pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. It is conjectured that for all graphs G and H, f(G×H)≤f(G)f(H). If the graph G satisfies the odd two-pebbling property, we will prove that f(C4k+3×G)≤f(C4k+3)f(G) and f(M(C2n)×G)≤f(M(C2n))f(G), where C4k+3 is the odd cycle of order 4k+3 and M(C2n) is the middle graph of the even cycle C2n.
This paper shows that, for any integers n and k with 0⩽k⩽n−2, at least (k+1)!(n−k−1) vertices or edges have to be removed from an n-dimensional star graph to make it disconnected and no vertices of degree less than k. The result gives an affirmative answer to the conjecture proposed by Wan and Zhang [Applied Mathematics Letters, 22 (2009), 264-267].
A subset F of edges in a connected graph G is a h-extra edge-cut if G−F is disconnected and every component has more than h vertices. The h-extra edge-connectivity $\la^{(h)}(G)$ of G is defined as the minimum cardinality over all h-extra edge-cuts of G. A graph G, if $\la^{(h)}(G)$ exists, is super-$\la^{(h)}$ if every minimum h-extra edge-cut of G isolates at least one connected subgraph of order h+1. The persistence ρ(h)(G) of a super-$\la^{(h)}$ graph G is the maximum integer m for which G−F is still super-$\la^{(h)}$ for any set F⊆E(G) with ∣F∣⩽m. Hong {\it et al.} [Discrete Appl. Math. 160 (2012), 579-587] showed that $\min\{\la^{(1)}(G)-δ(G)-1,δ(G)-1\}\leqslant ρ^{(0)}(G)\leqslant δ(G)-1$, where δ(G) is the minimum vertex-degree of G. This paper shows that $\min\{\la^{(2)}(G)-ξ(G)-1,δ(G)-1\}\leqslant ρ^{(1)}(G)\leqslant δ(G)-1$, where ξ(G) is the minimum edge-degree of G. In particular, for a k-regular super-$\la'$ graph G, ρ(1)(G)=k−1 if $\la^{(2)}(G)$ does not exist or G is super-$\la^{(2)}$ and triangle-free, from which the exact values of ρ(1)(G) are determined for some well-known networks.
Using some combinatorial techniques, in this note, it is proved that if α≥0.28866, then any digraph on n vertices with minimum outdegree at least αn contains a directed cycle of length at most 4.
As the size of a multiprocessor system increases, processor failure is inevitable, and fault identification in such a system is crucial for reliable computing. The fault diagnosis is the process of identifying faulty processors in a multiprocessor system through testing. For the practical fault diagnosis systems, the probability that all neighboring processors of a processor are faulty simultaneously is very small, and the conditional diagnosability, which is a new metric for evaluating fault tolerance of such systems, assumes that every faulty set does not contain all neighbors of any processor in the systems. This paper shows that the conditional diagnosability of bubble sort graphs Bn under the PMC model is 4n−11 for n≥4, which is about four times its ordinary diagnosability under the PMC model.
The varietal hypercube VQn is a variant of the hypercube Qn and has better properties than Qn with the same number of edges and vertices. This paper shows that every edge of VQn is contained in cycles of every length from 4 to 2n except 5, and every pair of vertices with distance d is connected by paths of every length from d to 2n−1 except 2 and 4 if d=1.
This paper considers a kind of generalized measure λs(h) of fault tolerance in a hypercube-like graph Gn which contain several well-known interconnection networks such as hypercubes, varietal hypercubes, twisted cubes, crossed cubes and Möbius cubes, and proves λs(h)(Gn)=2h(n−h) for any h with 0⩽h⩽n−1 by the induction on n and a new technique. This result shows that at least 2h(n−h) edges of Gn have to be removed to get a disconnected graph that contains no vertices of degree less than h. Compared with previous results, this result enhances fault-tolerant ability of the above-mentioned networks theoretically.
The growing size of the multiprocessor system increases its vulnerability to component failures. It is crucial to locate and to replace the faulty processors to maintain a system's high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. This paper shows that the largest connected component of the survival graph contains almost all remaining vertices in the (n,k)-arrangement graph An,k when the number of moved faulty vertices is up to twice or three times the traditional connectivity. Based on this fault resiliency, we establishes that the conditional diagnosability of An,k under the comparison model. We prove that for k≥4, n≥k+2, the conditional diagnosability of An,k is (3k−2)(n−k)−3; the conditional diagnosability of An,n−1 is 3n−7 for n≥5.
The augmented cube AQn, proposed by Choudum and Sunitha [S. A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], is a (2n−1)-regular (2n−1)-connected graph (n≥4). This paper determines that the 2-extra connectivity of AQn is 6n−17 for n≥9 and the 2-extra edge-connectivity is 6n−9 for n≥4. That is, for n≥9 (respectively, n≥4), at least 6n−17 vertices (respectively, 6n−9 edges) of AQn have to be removed to get a disconnected graph that contains no isolated vertices and isolated edges. When the augmented cube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system.
This paper considers a kind of generalized measure λs(h) of fault tolerance in the (n,k)-star graph Sn,k for 2⩽k⩽n−1 and 0⩽h⩽n−k, and determines λs(h)(Sn,k)=min{(n−h−1)(h+1),(n−k+1)(k−1)}, which implies that at least min{(n−k+1)(k−1),(n−h−1)(h+1)} edges of Sn,k have to remove to get a disconnected graph that contains no vertices of degree less than h. This result shows that the (n,k)-star graph is robust when it is used to model the topological structure of a large-scale parallel processing system.
This paper considers a kind of generalized measure κs(h) of fault tolerance in the (n,k)-star graph Sn,k and determines κs(h)(Sn,k)=n+h(k−2)−1 for 2⩽k⩽n−1 and 0⩽h⩽n−k, which implies that at least n+h(k−2)−1 vertices of Sn,k have to remove to get a disconnected graph that contains no vertices of degree less than h. This result contains some known results such as Yang et al. [Information Processing Letters, 110 (2010), 1007-1011].
The exchanged hypercube EH(s,t), proposed by Loh {\it et al.} [The exchanged hypercube, IEEE Transactions on Parallel and Distributed Systems 16 (9) (2005) 866-874], is obtained by removing edges from a hypercube Qs+t+1. This paper considers a kind of generalized measures κ(h) and λ(h) of fault tolerance in EH(s,t) with 1⩽s⩽t and determines κ(h)(EH(s,t))=λ(h)(EH(s,t))=2h(s+1−h) for any h with 0⩽h⩽s. The results show that at least 2h(s+1−h) vertices (resp. 2h(s+1−h) edges) of EH(s,t) have to be removed to get a disconnected graph that contains no vertices of degree less than h, and generalizes some known results.
This paper considers the problem of many-to-many disjoint paths in the hypercube Qn with f faulty vertices and obtains the following result. For any integer k with 1≤k≤n−2, any two sets S and T of k fault-free vertices in different parts of Qn (n≥3), if f≤2n−2k−3 and each fault-free vertex has at least two fault-free neighbors, then there exist k fully disjoint fault-free paths linking S and T which contain at least 2n−2f vertices. This result improves some known results in a sense.
The bondage number of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number of G. This lecture gives a survey on the bondage number, including the known results, problems and conjectures. We also summarize other types of bondage numbers.
Let G1 and G2 be two undirected nontrivial graphs. The Kronecker product of G1 and G2 denoted by G1⊗G2 with vertex set V(G1)×V(G2), two vertices x1x2 and y1y2 are adjacent if and only if (x1,y1)∈E(G1) and (x2,y2)∈E(G2). This paper presents a formula for computing the diameter of G1⊗G2 by means of the diameters and primitive exponents of factor graphs.
For a simple digraph G, let β(G) be the size of the smallest subset X⊆E(G) such that G−X has no directed cycles, and let γ(G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called m-free if G has no directed cycles of length at most m. This paper proves that β(G)≤m−21γ(G) for any m-free digraph G, which generalized some known results.
Let G=(V,E) be a graph and p be a positive integer. A subset S⊆V is called a p-dominating set if each vertex not in S has at least p neighbors in S. The p-domination number $\g_p(G)$ is the size of a smallest p-dominating set of G. The p-reinforcement number rp(G) is the smallest number of edges whose addition to G results in a graph G′ with $\g_p(G')<\g_p(G)$. In this paper, we give an original study on the p-reinforcement, determine rp(G) for some graphs such as paths, cycles and complete t-partite graphs, and establish some upper bounds of rp(G). In particular, we show that the decision problem on rp(G) is NP-hard for a general graph G and a fixed integer p≥2.
A Roman dominating function on a graph G=(V,E) is a function f:V→{0,1,2} such that every vertex v∈V with f(v)=0 has at least one neighbor u∈V with f(u)=2. The weight of a Roman dominating function is the value f(V(G))=∑u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number, denoted by γR(G). The Roman bondage number bR(G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E′⊆E(G) for which γR(G−E′)>γR(G). In this paper, we first show that the decision problem for determining bR(G) is NP-hard even for bipartite graphs and then we establish some sharp bounds for bR(G) and characterizes all graphs attaining some of these bounds.
Many real-world phenomena can be represented by a spatio-temporal signal: where, when, and how much. Social media is a tantalizing data source for those who wish to monitor such signals. Unlike most prior work, we assume that the target phenomenon is known and we are given a method to count its occurrences in social media. However, counting is plagued by sample bias, incomplete data, and, paradoxically, data scarcity -- issues inadequately addressed by prior work. We formulate signal recovery as a Poisson point process estimation problem. We explicitly incorporate human population bias, time delays and spatial distortions, and spatio-temporal regularization into the model to address the noisy count issues. We present an efficient optimization algorithm and discuss its theoretical properties. We show that our model is more accurate than commonly-used baselines. Finally, we present a case study on wildlife roadkill monitoring, where our model produces qualitatively convincing results.
Let p be a positive integer and G=(V,E) be a simple graph. A subset D⊆V is a p-dominating set if each vertex not in D has at least p neighbors in D. The p-domination number $\g_p(G)$ is the minimum cardinality among all p-dominating sets of G. The p-bondage number bp(G) is the cardinality of a smallest set of edges whose removal from G results in a graph with a p-domination number greater than the p-domination number of G. In this note we determine the 2-domination number $\g_2$ and 2-bondage number b2 for the grid graphs Gm,n=Pm×Pn for 2≤m≤4.
A routing R of a given connected graph G of order n is a collection of n(n−1) simple paths connecting every ordered pair of vertices of G. The vertex-forwarding index ξ(G,R) of G with respect to R is defined as the maximum number of paths in R passing through any vertex of G. The vertex-forwarding index ξ(G) of G is defined as the minimum ξ(G,R) over all routing R's of G. Similarly, the edge-forwarding index π(G,R) of G with respect to R is the maximum number of paths in R passing through any edge of G. The edge-forwarding index π(G) of G is the minimum π(G,R) over all routing R's of G. The vertex-forwarding index or the edge-forwarding index corresponds to the maximum load of the graph. Therefore, it is important to find routings minimizing these indices and thus has received much research attention in the past ten years and more. In this paper we survey some known results on these forwarding indices, further research problems and several conjectures.
Let G=(V,E) be a graph and p a positive integer. A subset S⊆V is called a p-dominating set of G if every vertex not in S has at least p neighbors in S. The p-domination number is the minimum cardinality of a p-dominating set in G. In this paper, we establish an exact formula of the p-domination number of all complete multipartite graphs for arbitrary positive integer p.
The varietal hypercube VQn is a variant of the hypercube Qn and has better properties than Qn with the same number of edges and vertices. This paper proves that VQn is vertex-transitive. This property shows that when VQn is used to model an interconnection network, it is high symmetrical and obviously superior to other variants of the hypercube such as the crossed cube.
Let G=(V,E) be a graph and p a positive integer. The p-domination number $\g_p(G)$ is the minimum cardinality of a set D⊆V with ∣NG(x)∩D∣≥p for all x∈V∖D. The p-reinforcement number rp(G) is the smallest number of edges whose addition to G results in a graph G′ with $\g_p(G')<\g_p(G)$. Recently, it was proved by Lu et al. that rp(T)≤p+1 for a tree T and p≥2. In this paper, we characterize all trees attaining this upper bound for p≥3.
Let G=(V,E) be a graph. A subset D⊆V is a dominating set if every vertex not in D is adjacent to a vertex in D. A dominating set D is called a total dominating set if every vertex in D is adjacent to a vertex in D. The domination (resp. total domination) number of G is the smallest cardinality of a dominating (resp. total dominating) set of G. The bondage (resp. total bondage) number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with larger domination (resp. total domination) number of G. The reinforcement number of G is the smallest number of edges whose addition to G results in a graph with smaller domination number. This paper shows that the decision problems for bondage, total bondage and reinforcement are all NP-hard.
The Roman dominating function on a graph G=(V,E) is a function f:V→{0,1,2} such that each vertex x with f(x)=0 is adjacent to at least one vertex y with f(y)=2. The value f(G)=u∈V(G)∑f(u) is called the weight of f. The Roman domination number γR(G) is defined as the minimum weight of all Roman dominating functions. This paper defines the Roman bondage number bR(G) of a nonempty graph G=(V,E) to be the cardinality among all sets of edges B⊆E for which γR(G−B)>γR(G). Some bounds are obtained for bR(G), and the exact values are determined for several classes of graphs. Moreover, the decision problem for bR(G) is proved to be NP-hard even for bipartite graphs.
Let G=(V,E) be a graph. A subset D⊆V is a dominating set if every vertex not in D is adjacent to a vertex in D. The domination number of G is the smallest cardinality of a dominating set of G. The bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with larger domination number of G. In this paper, we determine that the exact value of the bondage number of (n−3)-regular graph G of order n is n−3.
The bondage number b(G) of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with domination number greater than that of G. Denote Pn×Pm be the Cartesian product of two paths Pn and Pm. This paper determines that the exact value of b(Pn×P2), b(Pn×P3) and b(Pn×P4) for n≥2.
The total domination number of a graph G without isolated vertices is the minimum number of vertices that dominate all vertices in G. The total bondage number bt(G) of G is the minimum number of edges whose removal enlarges the total domination number. This paper considers grid graphs. An (n,m)-grid graph Gn,m is defined as the cartesian product of two paths Pn and Pm. This paper determines the exact values of bt(Gn,2) and bt(Gn,3), and establishes some upper bounds of bt(Gn,4).
Let G be a graph without isolated vertices. The total domination number of G is the minimum number of vertices that can dominate all vertices in G, and the paired domination number of G is the minimum number of vertices in a dominating set whose induced subgraph contains a perfect matching. This paper determines the total domination number and the paired domination number of the toroidal meshes, i.e., the Cartesian product of two cycles Cn and Cm for any n≥3 and m∈{3,4}, and gives some upper bounds for n,m≥5.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.