Source author record

Yanxia Dong

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Extremal hypergraphs for matching number and domination number

A matching in a hypergraph $\mathcal{H}$ is a set of pairwise disjoint hyperedges. The matching number $ν(\mathcal{H})$ of $\mathcal{H}$ is the size of a maximum matching in $\mathcal{H}$ . A subset $D$ of vertices of $\mathcal{H}$ is a dominating set of $\mathcal{H}$ if for every $v\in V\setminus D$ there exists $u\in D$ such that $u$ and $v$ lie in an hyperedge of $\mathcal{H}$ . The cardinality of a minimum dominating set of $\mathcal{H}$ is the domination number of $\mathcal{H}$ , denoted by $γ(\mathcal{H})$ . It was proved that $γ(\mathcal{H})\leq (r-1)ν(\mathcal{H})$ for $r$ -uniform hypergraphs and the 2-uniform hypergraphs (graphs) achieving equality $γ(\mathcal{H})=ν(\mathcal{H})$ have been characterized. In this paper we generalize the inequality $γ(\mathcal{H})\leq (r-1)ν(\mathcal{H})$ to arbitrary hypergraph of rank $r$ and we completely characterize the extremal hypergraphs $\mathcal{H}$ of rank $3$ achieving equality $γ(\mathcal{H})=(r-1)ν(\mathcal{H})$ .

preprint2015arXiv

The distance domination of generalized de Bruijn and Kautz digraphs

Let $G=(V,A)$ be a digraph and $k\ge 1$ an integer. For $u,v\in V$ , we say that the vertex $u$ distance $k$ -dominate $v$ if the distance from $u$ to $v$ at most $k$ . A set $D$ of vertices in $G$ is a distance $k$ -dominating set if for each vertex of $V\setminus D$ is distance $k$ -dominated by some vertex of $D$ . The {\em distance $k$ -domination number} of $G$ , denoted by $γ_{k}(G)$ , is the minimum cardinality of a distance $k$ -dominating set of $G$ . Generalized de Bruijn digraphs $G_B(n,d)$ and generalized Kautz digraphs $G_K(n,d)$ are good candidates for interconnection networks. Tian and Xu showed that $\big \lceil n\big/\sum_{j=0}^kd^j\big\rceil\le γ_{k}(G_B(n,d))\le \big\lceil n/d^{k}\big\rceil$ and $\big \lceil n \big/\sum_{j=0}^kd^j\big\rceil\le γ_{k}(G_K(n,d))\le \big\lceil n/d^{k}\big\rceil$ . In this paper we prove that every generalized de Bruijn digraph $G_B(n,d)$ has the distance $k$ -domination number $\big\lceil n\big/\sum_{j=0}^kd^j\big\rceil$ or $\big\lceil n\big/\sum_{j=0}^kd^j\big\rceil+1$ , and the distance $k$ -domination number of every generalized Kautz digraph $G_K(n,d)$ bounded above by $\big\lceil n\big/(d^{k-1}+d^{k})\big\rceil$ . Additionally, we present various sufficient conditions for $γ_{k}(G_B(n,d))=\big\lceil n\big/\sum_{j=0}^kd^j\big\rceil$ and $γ_{k}(G_K(n,d))=\big\lceil n\big/\sum_{j=0}^kd^j\big\rceil$ .

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.