Songling Shan

activity

20132026

most citedNonempty Intersection of Longest Paths in Series-Parallel Graphs

33 citations · 69 across the 48 of their papers we have counts for

collaborators

54 papers

math.CO2026

Total Vertex Irregularity Strength of Cubic and 4-Regular Graphs

Songling Shan, Yucheng Zhong

Let $G$ be a graph and $k$ be a positive integer. A total $k$ -labeling of $G$ assigns to each vertex and each edge a label from ${1, \dots, k}$ . The weight of a vertex is the sum…

math.CO2026

Graceful Labeling of Two Families of Spiders

Songling Shan, Yucheng Zhong

A \emph{graceful labeling} of a graph $G$ is an injective function $f : V (G) \to {0, \dots, ∣ E (G) ∣}$ such that ${∣ f (u) - f (v) ∣ : uv \in E (G)} = {1, \dots, ∣ E (G) ∣}$ . If su…

math.CO2024

Vertex-distinguishing and sum-distinguishing edge coloring of regular graphs

Yuping Gao, Songling Shan, Guanghui Wang

Given an integer $k \geq 1$ , an edge- $k$ -coloring of a graph $G$ is an assignment of $k$ colors $1, \dots, k$ to the edges of $G$ such that no two adjacent edges receive the same color…

math.CO2024

Total coloring graphs with large maximum degree

Aseem Dalal, Jessica McDonald, Songling Shan

We prove that for any graph $G$ , the total chromatic number of $G$ is at most $Δ (G) + 2 ⌈ \frac{∣ V ( G ) ∣}{Δ ( G ) + 1} ⌉$ . This saves one color in comparison with a resu…

math.CO2024

Linear arboricity of robust expanders

Yuping Gao, Songling Shan

In 1980, Akiyama, Exoo, and Harary conjectured that any graph $G$ can be decomposed into at most $⌈(Δ (G) + 1) /2 ⌉$ linear forests. We confirm the conjecture for robust expan…

math.CO2024

Spanning Euler Tours in Hypergraphs

Amin Bahmanian, Songling Shan

Motivated by generalizations of de Bruijn cycles to various combinatorial structures (Chung, Diaconis, and Graham), we study various Euler tours in set systems. Let $G$ b…

math.CO2023

Triangle-degree and triangle-distinct graphs

Zhanar Berikkyzy, Beth Bjorkman, Heather Smith Blake +5

Let $G$ be a simple graph and $v$ be a vertex of $G$ . The triangle-degree of $v$ in $G$ is the number of triangles that contain $v$ . While every graph has at least two vertices wit…

math.CO2023

Towards the Overfull Conjecture

Songling Shan

Let $G$ be a simple graph with maximum degree denoted as $Δ (G)$ . An overfull subgraph $H$ of $G$ is a subgraph satisfying the condition $|E(H)| > Δ(G)\lfloor \frac{1}{2}|V(H)| \rfl…

math.CO2023

A note on Gupta's co-density conjecture

Guantao Chen, Songling Shan

Let $G$ be a multigraph. A subset $F$ of $E (G)$ is an edge cover of $G$ if every vertex of $G$ is incident to an edge of $F$ . The cover index, $ξ (G)$ , is the largest number of edge…

math.CO2023

A sufficient condition for a hypergraph to have a Berge- $k$ -factor

Yuping Gao, Songling Shan, Gexin Yu

For any graph (hypergraph) $G$ with vertex set $V$ and edge set $E$ , we define its incidence bipartite graph $I (G)$ as the bipartite graph with bipartition $(E, V)$ , wher…

math.CO2023

On the Multigraph Overfull Conjecture

Michael J. Plantholt, Songling Shan

A subgraph $H$ of a multigraph $G$ is overfull if $∣ E (H) ∣ > Δ (G) ⌊ ∣ V (H) ∣/2 ⌋$ . Analogous to the Overfull Conjecture proposed by Chetwynd and Hilton in 1986, Stiebitz…

math.CO2022

A construction of a $\frac{3}{2}$ -tough plane triangulation with no 2-factor

Songling Shan

In 1956, Tutte proved the celebrated theorem that every 4-connected planar graph is hamiltonian. This result implies that every more than $\frac{3}{2}$ -tough planar graph on at lea…

math.CO2022

An Ore-type condition for hamiltonicity in tough graphs and the extremal examples

Masahiro Sanka, Songling Shan

Let $G$ be a $t$ -tough graph on $n \geq 3$ vertices for some $t > 0$ . It was shown by Bauer et al. in 1995 that if the minimum degree of $G$ is greater than $\frac{n}{t + 1} - 1$ , then $G$ …

math.CO2022

Overfullness of edge-critical graphs with small minimal core degree

Yan Cao, Guantao Chen, Guangming Jing +1

Let $G$ be a simple graph. Denote by $n$ , $Δ (G)$ and $χ^{'} (G)$ be the order, the maximum degree and the chromatic index of $G$ , respectively. We call $G$ \emph{overfull} if $|E(G)|/…

math.CO2022

The overfull conjecture on graphs of odd order and large minimum degree

Songling Shan

Let $G$ be a simple graph with maximum degree $Δ (G)$ . A subgraph $H$ of $G$ is overfull if $∣ E (H) ∣ > Δ (G) ⌊ \frac{1}{2} ∣ V (H) ∣ ⌋$ . Chetwynd and Hilton in 1986 conjectured t…

math.CO2022

Existence of $2$ -Factors in Tough Graphs without Forbidden Subgraphs

Elizabeth Grimm, Songling Shan, Anna Johnsen

For a given graph $R$ , a graph $G$ is $R$ -free if $G$ does not contain $R$ as an induced subgraph. It is known that every $2$ -tough graph with at least three vertices has a $2$ -fac…

math.CO2022

Precoloring extension of Vizing's Theorem for multigraphs

Yan Cao, Guantao Chen, Guangming Jing +2

Let $G$ be a graph with maximum degree $Δ (G)$ and maximum multiplicity $μ (G)$ . Vizing and Gupta, independently, proved in the 1960s that the chromatic index of $G$ is at most $Δ(G)…

math.CO2022

A note on hamiltonian cycles in $4$ -tough $(P_{2} \cup k P_{1})$ -free graphs

Lingjuan Shi, Songling Shan

Let $t > 0$ be a real number and $G$ be a graph. We say $G$ is $t$ -tough if for every cutset $S$ of $G$ , the ratio of $∣ S ∣$ to the number of components of $G - S$ is at least $t$ . The…

math.CO2021

Antimagic Orientation of Forests

Songling Shan, Xiaowei Yu

An antimagic labeling of a digraph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to ${1, 2, \dots, m}$ such that all $n$ oriented vertex-sums are pa…

math.CO2021

Erdős-Gyárfás Conjecture for $P_{8}$ -free graphs

Yuping Gao, Songling Shan

A graph is $P_{8}$ -free if it contains no induced subgraph isomorphic to the path $P_{8}$ on eight vertices. In 1995, Erdős and Gyárfás conjectured that every graph of minimum degree a…

math.CO2021

The Core Conjecture of Hilton and Zhao II: a Proof

Yan Cao, Guantao Chen, Guangming Jing +1

A simple graph $G$ with maximum degree $Δ$ is overfull if $∣ E (G) ∣ > Δ ⌊ ∣ V (G) ∣/2 ⌋$ . The core of $G$ , denoted $G_{Δ}$ , is the subgraph of $G$ induced by its vertices of degre…

math.CO2021★ 1 cited

Pseudo-multifan and Lollipop

Yan Cao, Guantao Chen, Guangming Jing +1

A simple graph $G$ with maximum degree $Δ$ is \emph{overfull} if $∣ E (G) ∣ > Δ ⌊ ∣ V (G) ∣/2 ⌋$ . The \emph{core} of $G$ , denoted $G_{Δ}$ , is the subgraph of $G$ induced by its ver…

math.CO2021

Hamiltonian cycles in 7-tough $(P_{3} \cup 2 P_{1})$ -free graphs

Yuping Gao, Songling Shan

The toughness of a noncomplete graph $G$ is the maximum real number $t$ such that the ratio of $∣ S ∣$ to the number of components of $G - S$ is at least $t$ for every cutset $S$ of $G…

math.CO2021

Antimagic orientation of subdivided caterpillars

Jessica Ferraro, Genevieve Newkirk, Songling Shan

Let $m \geq 1$ be an integer and $G$ be a graph with $m$ edges. We say that $G$ has an antimagic orientation if $G$ has an orientation $D$ and a bijection $τ:A(D)\rightarrow \{1,2,\l…

Total Vertex Irregularity Strength of Cubic and 4-Regular Graphs

Graceful Labeling of Two Families of Spiders

Vertex-distinguishing and sum-distinguishing edge coloring of regular graphs

Total coloring graphs with large maximum degree

Linear arboricity of robust expanders

Spanning Euler Tours in Hypergraphs

Triangle-degree and triangle-distinct graphs

Towards the Overfull Conjecture

A note on Gupta's co-density conjecture

A sufficient condition for a hypergraph to have a Berge-k-factor

On the Multigraph Overfull Conjecture

A construction of a 23​-tough plane triangulation with no 2-factor

An Ore-type condition for hamiltonicity in tough graphs and the extremal examples

Overfullness of edge-critical graphs with small minimal core degree

The overfull conjecture on graphs of odd order and large minimum degree

Existence of 2-Factors in Tough Graphs without Forbidden Subgraphs

Precoloring extension of Vizing's Theorem for multigraphs

A note on hamiltonian cycles in 4-tough (P2​∪kP1​)-free graphs

Antimagic Orientation of Forests

Erdős-Gyárfás Conjecture for P8​-free graphs

The Core Conjecture of Hilton and Zhao II: a Proof

Pseudo-multifan and Lollipop

Hamiltonian cycles in 7-tough (P3​∪2P1​)-free graphs

Antimagic orientation of subdivided caterpillars

A sufficient condition for a hypergraph to have a Berge- $k$ -factor

A construction of a $\frac{3}{2}$ -tough plane triangulation with no 2-factor

Existence of $2$ -Factors in Tough Graphs without Forbidden Subgraphs

A note on hamiltonian cycles in $4$ -tough $(P_{2} \cup k P_{1})$ -free graphs

Erdős-Gyárfás Conjecture for $P_{8}$ -free graphs

Hamiltonian cycles in 7-tough $(P_{3} \cup 2 P_{1})$ -free graphs