Source author record

Kexiang Xu

Kexiang Xu 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

5works

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.

preprint2022arXiv

Relating the total domination number and the annihilation number for quasi-trees and some composite graphs

The total domination number $γ_{t}(G)$ of a graph $G$ is the cardinality of a smallest set $D\subseteq V(G)$ such that each vertex of $G$ has a neighbor in $D$. The annihilation number $a(G)$ of $G$ is the largest integer $k$ such that there exist $k$ different vertices in $G$ with the degree sum at most $m(G)$. It is conjectured that $γ_{t}(G)\leq a(G)+1$ holds for every nontrivial connected graph $G$. The conjecture has been proved for graphs with minimum degree at least $3$, trees, certain tree-like graphs, block graphs, and cactus graphs. In the main result of this paper it is proved that the conjecture holds for quasi-trees. The conjecture is verified also for some graph constructions including bijection graphs, Mycielskians, and the newly introduced universally-identifying graphs.

preprint2021arXiv

The domination game played on diameter 2 graphs

Let $γ_g(G)$ be the game domination number of a graph $G$. It is proved that if ${\rm diam}(G) = 2$, then $γ_g(G) \le \left\lceil \frac{n(G)}{2} \right\rceil- \left\lfloor \frac{n(G)}{11}\right\rfloor$. The bound is attained: if ${\rm diam}(G) = 2$ and $n(G) \le 10$, then $γ_g(G) = \left\lceil \frac{n(G)}{2} \right\rceil$ if and only if $G$ is one of seven sporadic graphs with $n(G)\le 6$ or the Petersen graph, and there are exactly ten graphs of diameter $2$ and order $11$ that attain the bound.

preprint2020arXiv

Constructing new families of transmission irregular graphs

The transmission of a vertex $v$ of a graph $G$ is the sum of distances from $v$ to all the other vertices in $G$. A graph is transmission irregular if all of its vertices have pairwise different transmissions. A starlike tree $T(k_1,\ldots,k_t)$ is a tree obtained by attaching to an isolated vertex $t$ pendant paths of lengths $k_1,\ldots,k_t$, respectively. It is proved that if a starlike tree $T(a,a+1,\ldots,a+k)$, $k\ge 2$, is of odd order, then it is transmission irregular. $T(1,2,\ldots,\ell)$, $\ell \ge 3$, is transmission irregular if and only if $\ell \notin \{r^2 + 1:\ r\ge 2\}$. Additional infinite families among the starlike trees and bi-starlike trees are determined. Transmission irregular unicyclic infinite families are also presented, in particular, the line graph of $T(a,a+1,a+2)$, $a\ge 2$, is transmission irregular if and only if $a$ is even.

preprint2020arXiv

On Rall's $1/2$-conjecture on the domination game

The $1/2$-conjecture on the domination game asserts that if $G$ is a traceable graph, then the game domination number $γ_g(G)$ of $G$ is at most $\left\lceil \frac{n(G)}{2} \right\rceil$. A traceable graph is a $1/2$-graph if $γ_g(G) = \left\lceil \frac{n(G)}{2} \right\rceil$ holds. It is proved that the so-called hatted cycles are $1/2$-graphs and that unicyclic graphs fulfill the $1/2$-conjecture. Several additional families of graphs that support the conjecture are determined and computer experiments related to the conjecture described.

preprint2016arXiv

Ordering connected graphs by their Kirchhoff indices

The Kirchhoff index $Kf(G)$ of a graph $G$ is the sum of resistance distances between all unordered pairs of vertices, which was introduced by Klein and Randić. In this paper we characterized all extremal graphs with Kirchhoff index among all graphs obtained by deleting $p$ edges from a complete graph $K_n$ with $p\leq\lfloor\frac{n}{2}\rfloor$ and obtained a sharp upper bound on the Kirchhoff index of these graphs. In addition, all the graphs with the first to ninth maximal Kirchhoff indices are completely determined among all connected graphs of order $n>27$.