BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Jun-Ming Xu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
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.
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\in V(G)$ and a real number $λ_m$ such that $d^{++}(v)\geq λ_m d^+(v)$, and $λ_m \rightarrow 1$ while $m \rightarrow +\infty$. 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\leq h\leq n-k$. This paper determines $κ_s^{(h)}=λ_s^{(h)}=\frac{(h+1)!(n-h-1)}{(n-k)!}$ for $n-k\leq h \leq 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 \geqslant 5$ and $1\leqslant s\leqslant d-3$, which answers a problem proposed ten years ago.
For an interconnection network $G$, the {\it $ω$-wide diameter} $d_ω(G)$ is the least $\ell$ such that any two vertices are joined by $ω$ internally-disjoint paths of length at most $\ell$, 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 $Q_{n,k}$ is a variant of the well-known hypercube. Yang, Chang, Pai, and Chan gave an upper bound for $d_{n+1}(Q_{n,k})$ and $D_{n+1}(Q_{n,k})$ and posed the problem of finding the wide diameters and fault diameters of $Q_{n,k}$. By constructing internally disjoint paths between any two vertices in the enhanced hypercube, for $n\ge3$ and $2\le k\le n$ we prove $$ D_ω(Q_{n,k})=d_ω(Q_{n,k})=\begin{cases} d(Q_{n,k}) & \textrm{for $1 \leq ω< n-\lfloor\frac{k}{2}\rfloor$;}\\ d(Q_{n,k})+1 & \textrm{for $n-\lfloor\frac{k}{2}\rfloor \leq ω\leq n+1$.} \end{cases} $$ where $d(Q_{n,k})$ is the diameter of $Q_{n,k}$. These results mean that interconnection networks modelled by enhanced hypercubes are extremely robust.
Let $G_n$ be an $n$-dimensional recursive network. The $h$-embedded connectivity $ζ_h(G_n)$ (resp. edge-connectivity $η_h(G_n)$) of $G_n$ is the minimum number of vertices (resp. edges) whose removal results in disconnected and each vertex is contained in an $h$-dimensional subnetwork $G_h$. This paper determines $ζ_h$ and $η_h$ for the hypercube $Q_n$ and the star graph $S_n$, and $η_3$ for the bubble-sort network $B_n$.
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 $t_c(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 $t_c(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\times H)\leq f(G)f(H)$. If the graph $G$ satisfies the odd two-pebbling property, we will prove that $f(C_{4k+3}\times G)\leq f(C_{4k+3})f(G)$ and $f(M(C_{2n})\times G)\leq f(M(C_{2n}))f(G)$, where $C_{4k+3}$ is the odd cycle of order $4k+3$ and $M(C_{2n})$ is the middle graph of the even cycle $C_{2n}$.
This paper shows that, for any integers $n$ and $k$ with $0\leqslant k \leqslant 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\subseteq E(G)$ with $|F|\leqslant 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 $α\geq 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 $B_n$ under the PMC model is $4n-11$ for $n \geq 4$, which is about four times its ordinary diagnosability under the PMC model.
The varietal hypercube $VQ_n$ is a variant of the hypercube $Q_n$ and has better properties than $Q_n$ with the same number of edges and vertices. This paper shows that every edge of $VQ_n$ is contained in cycles of every length from 4 to $2^n$ except 5, and every pair of vertices with distance $d$ is connected by paths of every length from $d$ to $2^n-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 $G_n$ which contain several well-known interconnection networks such as hypercubes, varietal hypercubes, twisted cubes, crossed cubes and Möbius cubes, and proves $λ_s^{(h)}(G_n)= 2^h(n-h)$ for any $h$ with $0\leqslant h\leqslant n-1$ by the induction on $n$ and a new technique. This result shows that at least $2^h(n-h)$ edges of $G_n$ 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 $A_{n,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 $A_{n,k}$ under the comparison model. We prove that for $k\geq 4$, $n\geq k+2$, the conditional diagnosability of $A_{n,k}$ is $(3k-2)(n-k)-3$; the conditional diagnosability of $A_{n,n-1}$ is $3n-7$ for $n\geq 5$.
The augmented cube $AQ_n$, 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\ge 4)$. This paper determines that the 2-extra connectivity of $AQ_n$ is $6n-17$ for $n\geq 9$ and the 2-extra edge-connectivity is $6n-9$ for $n\geq 4$. That is, for $n\geq 9$ (respectively, $n\geq 4$), at least $6n-17$ vertices (respectively, $6n-9$ edges) of $AQ_n$ 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 $S_{n,k}$ for $2\leqslant k \leqslant n-1$ and $0\leqslant h \leqslant n-k$, and determines $λ_s^{(h)}(S_{n,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 $S_{n,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 $S_{n,k}$ and determines $κ_s^{(h)}(S_{n,k})=n+h(k-2)-1$ for $2 \leqslant k \leqslant n-1$ and $0\leqslant h \leqslant n-k$, which implies that at least $n+h(k-2)-1$ vertices of $S_{n,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 $Q_{s+t+1}$. This paper considers a kind of generalized measures $κ^{(h)}$ and $λ^{(h)}$ of fault tolerance in $EH(s,t)$ with $1\leqslant s\leqslant t$ and determines $κ^{(h)}(EH(s,t))=λ^{(h)}(EH(s,t))= 2^h(s+1-h)$ for any $h$ with $0\leqslant h\leqslant s$. The results show that at least $2^h(s+1-h)$ vertices (resp. $2^h(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 $Q_n$ with $f$ faulty vertices and obtains the following result. For any integer $k$ with $1\leq k\leq n-2$, any two sets $S$ and $T$ of $k$ fault-free vertices in different parts of $Q_n\ (n\geq 3)$, if $f\leq 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 $2^n-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 $G_1$ and $G_2$ be two undirected nontrivial graphs. The Kronecker product of $G_1$ and $G_2$ denoted by $G_1\otimes G_2$ with vertex set $V(G_1)\times V(G_2)$, two vertices $x_1x_2$ and $y_1y_2$ are adjacent if and only if $(x_1,y_1)\in E(G_1)$ and $(x_2,y_2)\in E(G_2)$. This paper presents a formula for computing the diameter of $G_1\otimes G_2$ 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\subseteq 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)\leq \frac{1}{m-2}γ(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\subseteq 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 $r_p(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 $r_p(G)$ for some graphs such as paths, cycles and complete $t$-partite graphs, and establish some upper bounds of $r_p(G)$. In particular, we show that the decision problem on $r_p(G)$ is NP-hard for a general graph $G$ and a fixed integer $p\geq 2$.
A Roman dominating function on a graph $G=(V,E)$ is a function $f:V\rightarrow\{0,1,2\}$ such that every vertex $v\in V$ with $f(v)=0$ has at least one neighbor $u\in V$ with $f(u)=2$. The weight of a Roman dominating function is the value $f(V(G))=\sum_{u\in 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 $b_{R}(G)$ of a graph $G$ with maximum degree at least two is the minimum cardinality of all sets $E'\subseteq E(G)$ for which $γ_{R}(G-E')>γ_R(G)$. In this paper, we first show that the decision problem for determining $b_{\rm R}(G)$ is NP-hard even for bipartite graphs and then we establish some sharp bounds for $b_{\rm R}(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\subseteq 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 $b_p(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 $b_2$ for the grid graphs $G_{m,n}=P_m\times P_n$ for $2\leq m\leq 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\subseteq 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 $VQ_n$ is a variant of the hypercube $Q_n$ and has better properties than $Q_n$ with the same number of edges and vertices. This paper proves that $VQ_n$ is vertex-transitive. This property shows that when $VQ_n$ 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\subseteq V$ with $|N_G(x)\cap D|\geq p$ for all $x\in V\setminus D$. The $p$-reinforcement number $r_p(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 $r_p(T)\leq p+1$ for a tree $T$ and $p\geq 2$. In this paper, we characterize all trees attaining this upper bound for $p\geq 3$.
Let $G=(V,E)$ be a graph. A subset $D\subseteq 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\rightarrow\{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)=\sum\limits_{u\in V(G)} f(u)$ is called the weight of $f$. The Roman domination number $γ_{\rm R}(G)$ is defined as the minimum weight of all Roman dominating functions. This paper defines the Roman bondage number $b_{\rm R}(G)$ of a nonempty graph $G=(V,E)$ to be the cardinality among all sets of edges $B\subseteq E$ for which $γ_{\rm R}(G-B)>γ_{\rm R}(G)$. Some bounds are obtained for $b_{\rm R}(G)$, and the exact values are determined for several classes of graphs. Moreover, the decision problem for $b_{\rm R}(G)$ is proved to be NP-hard even for bipartite graphs.
Let $G=(V,E)$ be a graph. A subset $D\subseteq 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 $P_n\times P_m$ be the Cartesian product of two paths $P_n$ and $P_m$. This paper determines that the exact value of $b(P_n\times P_2)$, $b(P_n\times P_3)$ and $b(P_n\times P_4)$ for $n\ge 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 $b_t(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 $G_{n,m}$ is defined as the cartesian product of two paths $P_n$ and $P_m$. This paper determines the exact values of $b_t(G_{n,2})$ and $b_t(G_{n,3})$, and establishes some upper bounds of $b_t(G_{n,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 $C_n$ and $C_m$ for any $n\ge 3$ and $m\in\{3,4\}$, and gives some upper bounds for $n, m\ge 5$.