Source author record

Yingzhi Tian

Yingzhi Tian 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.

preprint2022arXiv

Super connected direct product of graphs and cycles

The topology of an interconnection network can be modeled by a graph $G=(V(G),E(G))$. The connectivity of graph $G$ is a parameter to measure the reliability of corresponding network. Direct product is one important graph product. This paper mainly focuses on the super connectedness of direct product of graphs and cycles. The connectivity of $G$, denoted by $κ(G)$, is the size of a minimum vertex set $S\subseteq V(G)$ such that $G-S$ is not connected or has only one vertex. The graph $G$ is said to be super connected, simply super-$κ$, if every minimum vertex cut is the neighborhood of a vertex with minimum degree. The direct product of two graphs $G$ and $H$, denoted by $G\times H$, is the graph with vertex set $V(G \times H) = V (G)\times V (H)$ and edge set $E(G \times H) = \{(u_{1} ,v_{1} )(u_{2} ,v_{2} )|\ u_{1}u_{2} \in E(G), v_{1}v_{2} \in E(H)\}$. In this paper, we give some sufficient conditions for direct product $G\times C_{n}$ to be super connected, where $C_{n}$ is the cycle on $n$ vertices. Furthermore, those sufficient conditions are best possible.

preprint2022arXiv

The $g$-extra connectivity of the strong product of paths and cycles

Let $G$ be a connected graph and $g$ be a non-negative integer. The $g$-extra connectivity of $G$ is the minimum cardinality of a set of vertices in $G$, if it exists, whose removal disconnects $G$ and leaves every component with more than $g$ vertices. The strong product $G_1 \boxtimes G_2$ of graphs $G_1=(V_{1}, E_{1})$ and $G_2=(V_{2}, E_{2})$ is the graph with vertex set $V(G_1 \boxtimes G_2)=V_{1} \times V_{2}$, where two distinct vertices $(x_{1}, x_{2}), (y_{1}, y_{2}) \in V_{1} \times V_{2}$ are adjacent in $G_1 \boxtimes G_2$ if and only if $x_{i}=y_{i}$ or $x_{i} y_{i} \in E_{i}$ for $i=1, 2$. In this paper, we obtain the $g$-extra connectivity of the strong product of two paths, the strong product of a path and a cycle, and the strong product of two cycles.

preprint2016arXiv

On restricted edge-connectivity of half-transitive multigraphs

Let $G=(V,E)$ be a multigraph (it has multiple edges, but no loops). The edge connectivity, denoted by $λ(G)$, is the cardinality of a minimum edge-cut of $G$. We call $G$ maximally edge-connected if $λ(G)=δ(G)$, and $G$ super edge-connected if every minimum edge-cut is a set of edges incident with some vertex. The restricted edge-connectivity $λ'(G)$ of $G$ is the minimum number of edges whose removal disconnects $G$ into non-trivial components. If $λ'(G)$ achieves the upper bound of restricted edge-connectivity, then $G$ is said to be $λ'$-optimal. A bipartite multigraph is said to be half-transitive if its automorphism group is transitive on the sets of its bipartition. In this paper, we will characterize maximally edge-connected half-transitive multigraphs, super edge-connected half-transitive multigraphs, and $λ'$-optimal half-transitive multigraphs.