Source author record

Meijie Ma

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Degree-associated edge-reconstruction numbers of double-brooms

An edge-deleted subgraph of a graph $G$ is an {\it edge-card}. A {\it decard} consists of an edge-card and the degree of the missing edge. The {\it degree-associated edge-reconstruction number} of a graph $G$ , denoted $\dern(G)$, is the minimum number of decards that suffice to reconstruct $G$ . The {\it adversary degree-associated edge-reconstruction number} $\adern(G)$ is the least $k$ such that every set of $k$ decards determines $G$ . We determine these two parameters for all double-brooms. The answer is usually $1$ for $\dern(G)$, and $2$ for $\adern(G)$ when $G$ is double-broom. But there are exceptions in each case.

preprint2016arXiv

The vulnerability of the diameter of enhanced hypercubes

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.

preprint2015arXiv

Cycles in enhanced hypercubes

The enhanced hypercube $Q_{n,k}$ is a variant of the hypercube $Q_n$ . We investigate all the lengths of cycles that an edge of the enhanced hypercube lies on. It is proved that every edge of $Q_{n,k}$ lies on a cycle of every even length from $4$ to $2^n$ ; if $k$ is even, every edge of $Q_{n,k}$ also lies on a cycle of every odd length from $k+3$ to $2^n-1$ , and some special edges lie on a shortest odd cycle of length $k+1$ .

preprint2015arXiv

Topological properties on the diameters of the integer simplex

Wide diameter $d_ω(G)$ and fault-diameter $D_ω(G)$ of an interconnection network $G$ have been recently studied by many authors. We determine the wide diameter and fault-diameter of the integer simplex $T_m^n$ . Note that $d_1(T_m^n)=D_1(T_m^n)= d(T_m^n)$ , where $d(T_m^n)$ is the diameter of $T_m^n$ . We prove that $d_ω(T_m^n)=D_ω(T_m^n)= d(T_m^n)+1$ when $2\leqω\leq n$ . Since a triangular pyramid $TP_L$ is $T_L^3$ , we have $d_ω(TP_L)=D_ω(TP_L)= d(TP_L)+1$ when $2\leqω\leq 3$ .

preprint2012arXiv

Fault-tolerant analysis of augmented cubes

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.

preprint2012arXiv

Many-to-many disjoint paths in hypercubes with faulty vertices

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.