Yaping Mao

Path connectivity of line graphs

Yaping Mao

Dirac showed that in a $(k - 1)$ -connected graph there is a path through each $k$ vertices. The path $k$ -connectivity $I ¨ _{k} (G)$ of a graph $G$ , which is a generalization of Dirac's n…

On the size edge-ordered Ramsey numbers of graphs

Yanyan Song, Yaping Mao

For edge-ordered graphs $G^{≺}$ and $H^{≺}$ , the size edge-ordered Ramsey number $r^_{edge} (G^{≺}, H^{≺})$ is defined as the smallest integer $m$ for wh…

Proper connection number and graph products

Yaping Mao, Fengnan Yanling, Zhao Wang +1

A path $P$ in an edge-colored graph $G$ is called \emph{a proper path} if no two adjacent edges of $P$ are colored the same, and $G$ is \emph{proper connected} if every two vertice…

The vertex-rainbow index of a graph

Yaping Mao

The $k$ -rainbow index $r x_{k} (G)$ of a connected graph $G$ was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the $k$ -rainbow index, we introduced th…

Diameter-Ramsey triangles below the $13 5^{\circ}$

Yaping Mao

A finite Euclidean set is diameter-Ramsey if, for every number of colors, some finite same-diameter witness has the property that every coloring of the witness contains a monochrom…

The Steiner 4-diameter of a graph

Zhao Wang, Yaping Mao, Hengzhe Li +1

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected…

On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

Hengzhe Li, Xueliang Li, Yaping Mao

The problem of determining the smallest number of edges, $h (n; I^ˉ º \geq r)$ , which guarantees that any graph with $n$ vertices and $h (n; I^ˉ º \geq r)$ edges will contain a pair of…

Multiplicity for partially ordered sets

Gyula O. H. Katona, Yaping Mao

Let $Q = {Q_{a} : a \geq 1}$ be a nested family of finite posets such that $Q_{a} \subseteq Q_{a + 1}$ and $∣ Q_{a} ∣ < ∣ Q_{a + 1} ∣$ . For a poset $Q$ , let $C_{t} (Q)$ denote the set of…

The minimal size of a graph with given generalized 3-edge-connectivity

Xueliang Li, Yaping Mao

For $S \subseteq V (G)$ and $∣ S ∣ \geq 2$ , $I^» (S)$ is the maximum number of edge-disjoint trees connecting $S$ in $G$ . For an integer $k$ with $2 \leq k \leq n$ , the \emph{generalized $k…

On two conjectures for generalized off-diagonal Schur numbers

Yanyan Song, Yaping Mao

For an integer $t \geq 3$ , let $L (t)$ denote the linear equation $x_{1} + x_{2} + \dots + x_{t - 1} = x_{t},$ where all variables are positive integers. For integers $k \geq 1$ …

math.CO2014

Additive codes over $GF (4)$ from circulant graphs

Ruihu Li, Xueliang Li, Yaping Mao +1

In $2006$ , Danielsen and Parker \cite{DP} proved that every self-dual additive code over $GF (4)$ is equivalent to a graph code. So, graph is an important tool for searching (propos…

On the set-coloring Ramsey numbers of graphs

Mengya He, Yaping Mao

The \textit{set-coloring Ramsey number} $R_{r, s} (G_{1}, G_{2}, ..., G_{r})$ is the least $n \in N$ such that every coloring $Ï: E\left(K_n\right) \rightarrow\binom{[r]}{…

Conflict-free connection numbers of line graphs

Bo Deng, Wenjing Li, Xueliang Li +2

A path in an edge-colored graph is called \emph{conflict-free} if it contains at least one color used on exactly one of its edges. An edge-colored graph $G$ is \emph{conflict-free…

Lower bounds for the spanning tree numbers of two graph products

Hengzhe Li, Xueliang Li, Yaping Mao +1

For any graph $G$ of order $n$ , the spanning tree packing number \emph{ $S T P (G)$ }, is the maximum number of edge-disjoint spanning trees contained in $G$ . In this paper, we obtain s…

On the $g$ -extra connectivity of graphs

Zhao Wang, Yaping Mao, Sun-Yuan Hsieh

Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network $G$ . In 1996, FÃ brega and Fiol proposed the $g$ -extra connectivit…

On the $g$ -good-neighbor connectivity of graphs

Zhao Wang, Yaping Mao, Sun-Yuan Hsieh +1

Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network $G$ . In 1996, FÃ brega and Fiol proposed the $g$ -good-neighbor con…

A survey on the generalized connectivity of graphs

Xueliang Li, Yaping Mao

The generalized $k$ -connectivity $I^º_{k} (G)$ of a graph $G$ was introduced by Hager before 1985. As its a natural counterpart, we introduced the concept of generalized edge-connectiv…

Steiner 3-diameter, maximum degree and size of a graph

Yaping Mao

The Steiner $k$ -diameter $s d ia m_{k} (G)$ of a graph $G$ , introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical diameter. W…

Ramsey Achievement Games on Graphs : Algorithms and Bounds

Xiumin Wang, Zhong Huang, Xiangqian Zhou +2

In 1982, Harary introduced the concept of Ramsey achievement game on graphs. Given a graph $F$ with no isolated vertices. Consider the following game played on the complete graph $…

Graphs with large generalized (edge-)connectivity

Xueliang Li, Yaping Mao

The generalized $k$ -connectivity $I^º_{k} (G)$ of a graph $G$ , introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart,…

A complete solution to the biased Alon-Krivelevich-Spencer-SzabÃ³ criterion problem for the discrepancy game

Yaping Mao, Meiqin Wei, Gang Yang

Let $H=(V,\mathcal E)$ be a finite hypergraph. For positive integers $p$ and $q$, the $(p:q)$-biased discrepancy game on $H$ is played in complete rounds. In each round,…

ErdÅs-GyÃ¡rfÃ¡s problem for partially ordered sets

Gyula O. H. Katona, Yaping Mao

Given integers $p, q, t$ with $1 \leq t \leq p$ and $1 \leq q \leq h_{p} (t)$ , a strong $(p, q, t)$ -coloring of the Boolean lattice $B_{n}$ is a coloring of its $t$ -chains such that every induc…

Complete bipartite graphs without small rainbow stars

Weizhen Chen, Meng Ji, Yaping Mao +1

The $k$ -edge-colored bipartite Gallai-Ramsey number $bgr_{k} (G : H)$ is defined as the minimum integer $n$ such that $n^{2} \geq k$ and for every $N \geq n$ , every edge-colo…

The minimal size of graphs with given pendant-tree connectivity

Yaping Mao

The concept of pendant-tree $k$ -connectivity $I ¨ _{k} (G)$ of a graph $G$ , introduced by Hager in 1985, is a generalization of classical vertex-connectivity. Let $f (n, k, ℓ)$ be the m…

On the minimum number of monochromatic solutions to the strict Schur inequality in 2-colored integer intervals with negative left endpoint

Gang Yang, Jinxia Liang, Yaping Mao +2

Kosek, Robertson, Sabo, and Schaal studied the minimum number $M_k(n)$ of monochromatic solutions to the strict Schur inequality system $x_{1} \leq x_{2} \leq x_{3}$ and $x_{1} + x_{2} < x_{3}$ in \…

Constructing disjoint Steiner trees in SierpiÅski graphs

Chenxu Yang, Ping Li, Yaping Mao +2

Let $G$ be a graph and $S \subseteq V (G)$ with $∣ S ∣ \geq 2$ . Then the trees $T_{1}, T_{2}, \dots, T_{ℓ}$ in $G$ are \emph{internally disjoint Steiner trees} connecting $S$ (or $S$ -Stei…

math.CO2012

Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

Xueliang Li, Yaping Mao

Let $G$ be a graph, $S$ be a set of vertices of $G$ , and $I^» (S)$ be the maximum number $ℓ$ of pairwise edge-disjoint trees $T_{1}, T_{2}, ..., T_{ℓ}$ in $G$ such that $S\subseteq…

Asymptotic Bounds for CO-irredundant and Irredundant Ramsey Numbers

Meng Ji, Yaping Mao, Ingo Schiermeyer

A set of vertices $X \subseteq V$ in a simple graph $G (V, E)$ is irredundant (CO-irredundant) if each vertex $x \in X$ is either isolated in the induced subgraph $G [X]$ or else has a…

Ramsey and Gallai-Ramsey numbers for linear forests and kipas

Ping Li, Yaping Mao, Ingo Schiermeyer +1

For two graphs $G, H$ , the \emph{Ramsey number} $r (G, H)$ is the minimum integer $n$ such that any red/blue edge-coloring of $K_{n}$ contains either a red copy of $G$ or a blue copy of…

Conflict-free vertex-connections of graphs

Xueliang Li, Yingying Zhang, Xiaoyu Zhu +2

A path in a vertex-colored graph is called \emph{conflict free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be \emph{conflict-free ve…

The Steiner diameter of a graph

Yaping Mao

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected…

On extremal graphs with at most $ℓ$ internally disjoint Steiner trees connecting any n-1 vertices

Xueliang Li, Yaping Mao

The concept of maximum local connectivity $I^ˉ º$ of a graph was introduced by BollobÃ¡s. One of the problems about it is to determine the largest number of edges $f(n;\barÎº\leq…

math.CO2020

Gallai-Ramsey number for the union of stars

Yaping Mao, Zhao Wang, Colton Magnant +1

Given a graph $G$ and a positive integer $k$ , define the \emph{Gallai-Ramsey number} to be the minimum number of vertices $n$ such that any $k$ -edge coloring of the complete graph…

Line k-Arboricity in Product Networks

Yaping Mao, Zhiwei Guo, Nan Jia +1

A \emph{linear $k$ -forest} is a forest whose components are paths of length at most $k$ . The \emph{linear $k$ -arboricity} of a graph $G$ , denoted by $la_{k} (G)$ , is the least n…

Monochromatic connectivity and graph products

Yaping Mao, Zhao Wang, Fengnan Yanling +1

The concept of monochromatic connectivity was introduced by Caro and Yuster. A path in an edge-colored graph is called a \emph{monochromatic path} if all the edges on the path are…

Bounds for Gallai-Ramsey functions and numbers

Zhao Wang, Yaping Mao, Ran Gu +2

For two graphs $G, H$ and a positive integer $k$ , the \emph{Gallai-Ramsey number} $gr_{k} (G, H)$ is defined as the minimum number of vertices $n$ such that any $k$ -edge-…

Gallai-Ramsey Multiplicity

Yaping Mao

Given two graphs $G$ and $H$ , the \emph{general $k$ -colored Gallai-Ramsey number} $gr_{k} (G : H)$ is defined to be the minimum integer $m$ such that every $k$ -coloring o…

Complete Resolution of the Butler-Costello-Graham Conjecture on Monochromatic Constellations

Gang Yang, Yaping Mao

A constellation pattern is a finite increasing rational sequence $Q=[0=q_0<q_1<\cdots<q_k=1]$, and a $Q$-constellation in $[n]$ is obtained by scaling and translating a ratio…

New upper bound for multicolor Ramsey numbers

Gang Yang, Yaping Mao

Let $R_{r} (k)$ denote the diagonal $r$ -color graph Ramsey number. We prove that there exist absolute constants $c, K > 0$ such that \[ R_r(k)\le \exp\!\left(-c\frac{k}{r^2\log^4(2r)}\ri…

Gallai-Ramsey numbers for books

Jinyu Zou, Yaping Mao, Colton Magnant +2

Given a graph $G$ and a positive integer $k$ , the \emph{Gallai-Ramsey number} is defined to be the minimum number of vertices $n$ such that any $k$ -edge coloring of $K_{n}$ contains…

Counterexamples to the Corsten-Frankl conjecture on diameter-Ramsey simplices

Yaping Mao

Corsten and Frankl conjectured that a simplex is diameter-Ramsey if and only if its circumcenter lies in its convex hull. We disprove this conjecture in every dimension $d \geq 3$ . T…

math.CO2022

On the distance-edge-monitoring numbers of graphs

Chengxu Yang, Ralf Klasing, Yaping Mao +1

Foucaud et al. [Discrete Appl. Math. 319 (2022), 424-438] recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. For a set…

Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks

Yaping Mao

The concept of pedant tree-connectivity was introduced by Hager in 1985. For a graph $G = (V, E)$ and a set $S \subseteq V (G)$ of at least two vertices, \emph{an $S$ -Steiner tree} or \…

cs.DM2024

Monitoring the edges of product networks using distances

Wen Li, Ralf Klasing, Yaping Mao +1

Foucaud {\it et al.} recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Let $G$ be a graph with vertex set $V (G)$ , $M$ …

cs.NI2022

A general approach to deriving diagnosability results of interconnection networks

Eddie Cheng, Yaping Mao, Ke Qiu +1

We generalize an approach to deriving diagnosability results of various interconnection networks in terms of the popular $g$ -good-neighbor and $g$ -extra fault-tolerant models, as w…

cs.DM2025

The $g$ -good-neighbor diagnosability of product networks under the PMC model

Zhao Wang, Yaping Mao, Sun-Yuan Hsieh +1

The concept of neighbor connectivity originated from the assessment of the subversion of espionage networks caused by underground resistance movements, and it has now been applied…

Note on the connectivity keeping spiders in $k$ -connected graphs

Meng Ji, Yaping Mao

W. Mader [J. Graph Theory 65 (2010), 61--69] conjectured that for any tree $T$ of order $m$ , every $k$ -connected graph $G$ with $I^´ (G) \geq ⌊ \frac{3 k}{2} ⌋ + m - 1$ contains a…

math.CO2022

Some multivariable Rado numbers

Gang Yang, Yaping Mao, Changxiang He +1

The Rado number of an equation is a Ramsey-theoretic quantity associated to the equation. Let $E$ be a linear equation. Denote by $R_{r} (E)$ the mi…

On the two problems in Ramsey achievement games

Zhong Huang, Yusuke Kobayashi, Yaping Mao +2

Let $p, q$ be two integers with $p \geq q$ . Given a finite graph $F$ with no isolated vertices, the generalized Ramsey achievement game of $F$ on the complete graph $K_{n}$ , denoted by…

Fractional matching preclusion for generalized augmented cubes

Tianlong Ma, Yaping Mao, Eddie Cheng +1

The \emph{matching preclusion number} of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. A…

Ramsey-TurÃ¡n theory for partially-ordered sets

Gyula O. H. Katona, Yaping Mao

We introduce weak and strong poset Ramsey-TurÃ¡n numbers for $t$ -chains in host poset families, focusing on the Boolean lattice family $B = {B_{n} : n \geq 1}$ . For any poset $…

Ramsey and Gallai-Ramsey numbers for stars with extra independent edges

Yaping Mao, Zhao Wang, Colton Magnant +1

Given a graph $G$ and a positive integer $k$ , define the \emph{Gallai-Ramsey number} to be the minimum number of vertices $n$ such that any $k$ -edge coloring of $K_{n}$ contains eith…

Steiner Distance in Graphs--A Survey

Yaping Mao

For a connected graph $G$ of order at least $2$ and $S \subseteq V (G)$ , the \emph{Steiner distance} $d_{G} (S)$ among the vertices of $S$ is the minimum size among all connected subgra…

Fractional matching preclusion number of graphs

Jinyu Zou, Yaping Mao, Zhao Wang +1

The \emph{fractional matching preclusion number} of a graph $G$ , denoted by $f m p (G)$ , is the minimum number of edges whose deletion results in a graph that has no fractional perfec…

Matching preclusion number of graphs

Zhao Wang, Yaping Mao, Eddie Cheng +1

The \emph{matching preclusion number} of a graph $G$ , denoted by $\mpo(G)$, is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor…

Pendant-tree connectivity of line graphs

Yaping Mao

The concept of pendant-tree connectivity, introduced by Hager in 1985, is a generalization of classical vertex-connectivity. In this paper, we study pendant-tree connectivity of li…

math.CO2014

Formally self-dual linear binary codes from circulant graphs

Ruihu Li, Xueliang Li, Yaping Mao +1

In 2002, Tonchev first constructed some linear binary codes defined by the adjacency matrices of undirected graphs. So, graph is an important tool for searching optimum codes. In t…

The ErdÅs-Faudree Problems and the Isolate-Free Core

Yaping Mao

In 1981, ErdÅs and Faudree asked whether there exists an infinite family of graphs $G_{N}$ on $N$ vertices with $I^ (G_{N}) < N - 1$ and $\sri(G_N)=1$, and whether every family with $|V(G_…

Ramsey multiplicity for ordered graphs

Mengya He, Yaping Mao, Bing Wei +1

Let $\cG_1,\ldots,\cG_k$ be fixed vertex-ordered graphs, each containing at least one edge. The ordered Ramsey number $\oR(\cG_1,\ldots,\cG_k)$ is the least integer $N$ such…

Asymptotic Bounds for t(3,n) and an Application to t(4,n)

Meng Ji, Yaping Mao, Ingo Schiermeyer

A set of vertices $X \subseteq V$ in a simple graph $G (V, E)$ is irredundant if each vertex $x \in X$ is either isolated in the induced subgraph $G [X]$ or else has a private neighbor…

Diagonal Ramsey numbers for wheels

Maoxuan Li, Masaki Kashima, Yaping Mao

The Ramsey number $R (G_{1}, G_{2})$ is the smallest integer $N$ such that any red-blue coloring of the edges of the complete graph $K_{N}$ contains either a red copy of $G_{1}$ or…

Steiner diameter, maximum degree and size of a graph

Yaping Mao, Zhao Wang

The Steiner diameter $s d ia m_{k} (G)$ of a graph $G$ , introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical diameter. When…

On the generalized (edge-)connectivity of graphs

Xueliang Li, Yaping Mao, Yuefang Sun

The generalized $k$ -connectivity $I^º_{k} (G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of generalized $k$ -edge-connectivity $Î…

Boolean lattice without small rainbow subposets

Gyula O. H. Katona, Yaping Mao, Kenta Ozeki +2

A Boolean lattice $B_{n} = (2^{X}, \leq)$ is the power set of an $n$ -element ground set $X$ equipped with inclusion relation. For two posets $P$ and $Q$ , we…

Gallai-Ramsey numbers for fans

Yaping Mao, Zhao Wang, Colton Magnant +1

Given a graph $G$ and a positive integer $k$ , define the \emph{Gallai-Ramsey number} to be the minimum number of vertices $n$ such that any $k$ -edge coloring of $K_{n}$ contains eith…

Steiner Distance in Product Networks

Yaping Mao, Eddie Cheng, Zhao Wang

For a connected graph $G$ of order at least $2$ and $S \subseteq V (G)$ , the \emph{Steiner distance} $d_{G} (S)$ among the vertices of $S$ is the minimum size among all connected subgra…

Ramsey and Gallai-Ramsey number for wheels

Yaping Mao, Zhao Wang, Colton Magnant +1

Given a graph $G$ and a positive integer $k$ , define the \emph{Gallai-Ramsey number} to be the minimum number of vertices $n$ such that any $k$ -edge coloring of $K_{n}$ contains eith…

Nordhaus-Gaddum-type theorem for conflict-free connection number of graphs

Hong Chang, Zhong Huang, Xueliang Li +2

An edge-colored graph $G$ is \emph{conflict-free connected} if, between each pair of distinct vertices, there exists a path containing a color used on exactly one of its edges. The…

Gallai-Schur Triples and Related Problems

Yaping Mao, Aaron Robertson, Jian Wang +2

Schur's Theorem states that, for any $r \in Z^{+}$ , there exists a minimum integer $S (r)$ such that every $r$ -coloring of ${1, 2, \dots, S (r)}$ admits a monochromatic solutio…

math.CO2022

Euclidean Gallai-Ramsey Theory

Yaping Mao, Kenta Oeki, Zhao Wang

In this paper, we introduce Euclidean Gallai-Ramsey theory, by combining Euclidean Ramsey theory and Gallai-Ramsey theory on graphs. More precisely, we consider the following probl…

math.CO2021

Gallai-Ramsey numbers involving a rainbow $4$ -path

Jinyu Zou, Zhao Wang, Hong-Jian Lai +1

Given two non-empty graphs $G, H$ and a positive integer $k$ , the Gallai-Ramsey number $gr_{k} (G : H)$ is defined as the minimum integer $N$ such that for all $n \geq N$ ,…

math.CO2021

Nordhaus-Guddum type results for the Steiner Gutman index of graphs

Zhao Wang, Yaping Mao, Kinkar Chandra Das +1

Building upon the notion of Gutman index $SGut (G)$ , Mao and Das recently introduced the Steiner Gutman index by incorporating Steiner distance for a connected graph…

math.CO2020

Gallai Ramsey number for double stars

Gyula O. H. Katona, Colton Magnant, Yaping Mao +1

Given a graph $G$ and a positive integer $k$ , the \emph{Gallai-Ramsey number} is defined to be the minimum number of vertices $n$ such that any $k$ -edge coloring of $K_{n}$ contains…

Steiner (revised) Szeged index of graphs

Modjtaba Ghorbani, Xueliang Li, Hamid Reza Maimani +3

The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph $G$ of order…

cs.DM2024

Perturbation results for distance-edge-monitoring numbers

Chenxu Yang, Ralf Klasing, Changxiang He +1

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph $G = (V (G), E (G))$ , a set $M \subseteq V(…

On the Equitable Vertex Arboricity of Graphs

Yaping Mao, Zhiwei Guo, Hongjian Lai +1

The equitable coloring problem, introduced by Meyer in 1973, has received considerable attention and research. Recently, Wu, Zhang and Li introduced the concept of equitable $(t,k)…

math.CO2012

Graphs with large generalized 3-connectivity

Hengzhe Li, Xueliang Li, Yaping Mao +1

Let $S$ be a nonempty set of vertices of a connected graph $G$ . A collection $T_{1}, ..., T_{ℓ}$ of trees in $G$ is said to be internally disjoint trees connecting $S$ if $E(T_i)\cap…

Induced Ramsey numbers for fans

Chuang Zhong, Masaki Kashima, Yaping Mao +1

The induced Ramsey number $r_{ind} (G, H)$ is defined as the minimum order of a graph $F$ on such that any 2-coloring of its edges with red and blue leads to either a red in…

From Halin's Edge Removability to Matching Removability in $k$ -Connected Graphs

Hengzhe Li, Mingming Zhou, Shinya Fujita +1

We study matching-removability under the degree/connectivity regime of Halin's theorem, which asserts that every $k$ -connected graph $G$ with minimum degree $I^´ (G) \geq k + 1$ contains…

Constructing edge-disjoint Steiner trees in Cartesian product networks

Rui Li, Gregory Gutin, He Zhang +3

Cartesian product networks are always regarded as a tool for ``combining'' two given networks with established properties to obtain a new one that inherits properties from both. Fo…

Ramsey-finiteness for graph pairs: A complete solution to the Burr-ErdÅs-Faudree-Schelp conjectures

Yaping Mao

For finite graphs $G$ and $H$ , let $\RR(G,H)$ denote the isomorphism classes of Ramsey-minimal graphs for $(G, H)$ . We prove two 1981 conjectures of Burr, ErdÅs, Faudree, Rousseau,…

Ramsey numbers for partially-ordered sets

Gyula O. H. Katona, Yaping Mao, Kenta Ozeki +1

We say that a poset $Q$ contains a copy (resp.~an induced copy) of a poset $P$ if there is an injection $f : P \to Q$ such that for any $x, y \in P$ , $f (x) \leq f (y)$ in $Q$ if (resp…

The Steiner (n-3)-diameter of a graph

Yaping Mao, Christopher Melekian, Eddie Cheng

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected…

On the equitable vertex arboricity of complete tripartite graphs

Zhiwei Guo, Haixing Zhao, Yaping Mao

The equitable coloring problem, introduced by Meyer in 1973, has received considerable attention and research. Recently, Wu et al. introduced the concept of equitable (t,k)-tree-co…

Further hardness results on the generalized connectivity of graphs

Lily Chen, Xueliang Li, Mengmeng Liu +1

The generalized $k$ -connectivity $I^º_{k} (G)$ of a graph $G$ was introduced by Chartrand et al. in 1984, which is a nice generalization of the classical connectivity. Recently, as a n…

math.CO2021

Gallai-Ramsey numbers of odd cycles

Zhao Wang, Yaping Mao, Colton Magnant +2

Given two graphs $G$ and $H$ and a positive integer $k$ , the $k$ -color Gallai-Ramsey number, denoted by $g r_{k} (G : H)$ , is the minimum integer $N$ such that for all $n \geq N$ , ev…

On the regular k-independence number of graphs

Zhiwei Guo, Haixing Zhao, Hongjian Lai +1

The \emph{regular independence number}, introduced by Albertson and Boutin in 1990, is the maximum cardinality of an independent set of $G$ in which all vertices have equal degree…

The generalized 3-connectivity of Lexicographic product graphs

Xueliang Li, Yaping Mao

The generalized $k$ -connectivity $I^º_{k} (G)$ of a graph $G$ , introduced by Chartrand et al., is a natural and nice generalization of the concept of (vertex-)connectivity. In this pap…

#tournament theory#graph inversion#decycling families#transitive tournaments

The inversion number of a path-reversed tournament: Resolving a conjecture of Belkhechine, Bouaziz, Boudabbous, and Pouzet

Yaping Mao

The paper proves that the inversion number of the path‑reversed tournament Q_n equals ⌊(n‑1)/2⌋, confirming a conjecture by Belkhechine et al.

Ramsey and Gallai-Ramsey numbers for two classes of unicyclic graphs

Zhao Wang, Yaping Mao, Colton Magnant +1

Given a graph $G$ and a positive integer $k$ , define the \emph{Gallai-Ramsey number} to be the minimum number of vertices $n$ such that any $k$ -edge coloring of $K_{n}$ contains eith…

Interval minors of complete multipartite graphs

Yaping Mao, Hongjian Lai, Zhao Wang +1

Interval minors of bipartite graphs were introduced by Jacob Fox in the study of Stanley-Wilf limits. Recently, Mohar, Rafiey, Tayfeh-Rezaie and Wu investigated the maximum number…

On the pedant tree-connectivity of graphs

Yaping Mao

The concept of pedant tree-connectivity was introduced by Hager in 1985. For a graph $G = (V, E)$ and a set $S \subseteq V (G)$ of at least two vertices, \emph{an $S$ -Steiner tree} or \…