Source author record

Xiaoya Zha

Xiaoya Zha appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO

Catalog footprint

What is connected

3works

1topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2016arXiv

Partial duality and closed 2-cell embeddings

In 2009 Chmutov introduced the idea of partial duality for embeddings of graphs in surfaces. We discuss some alternative descriptions of partial duality, which demonstrate the symmetry between vertices and faces. One is in terms of band decompositions, and the other is in terms of the gem (graph-encoded map) representation of an embedding. We then use these to investigate when a partial dual is a closed 2-cell embedding, in which every face is bounded by a cycle in the graph. We obtain a necessary and sufficient condition for a partial dual to be closed 2-cell, and also a sufficient condition for no partial dual to be closed 2-cell.

preprint2015arXiv

Thickness and Outerthickness for Embedded Graphs

We consider the thickness $θ(G))$ and outerthickness $θ_o(G)$ of a graph G in terms of its orientable and nonorientable genus. Dean and Hutchinson provided upper bounds for thickness of graphs in terms of their orientable genus. More recently, Concalves proved that the outerthickness of any planar graph is at most 2. In this paper, we apply the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness of graphs. We first obtain better upper bounds for thickness. We then use a similar approach to provide upper bounds for outerthickness of graphs in terms of their orientable and nonorientable genera. Finally we show that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. We also show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5.

preprint2014arXiv

Dominating Plane Triangulations

In 1996, Tarjan and Matheson proved that if $G$ is a plane triangulated disc with $n$ vertices, $γ(G)\le n/3$, where $γ(G)$ denotes the domination number of $G$. Furthermore, they conjectured that the constant $1/3$ could be improved to $1/4$ for sufficiently large $n$. Their conjecture remains unsettled. In the present paper, it is proved that if $G$ is a hamiltonian plane triangulation with $|V(G)|=n$ vertices and minimum degree at least 4, then $γ(G)\le\max\{\lceil 2n/7\rceil, \lfloor 5n/16\rfloor\}$. It follows immediately that if $G$ is a 4-connected plane triangulation with $n$ vertices, then $γ(G)\le\max\{\lceil 2n/7\rceil, \lfloor 5n/16\rfloor\} $. It then follows that if $n\ge 26$, then $γ(G)\le \lfloor 5n/16\rfloor$.