Schedule of the 2024 WVU Conference on Discrete Mathematics and Applications
— April 19-21, 2024
| Time | Event Title / Speaker / Details | |||
|---|---|---|---|---|
| 8:00-8:30
|
Registration
Lobby Outside of 202 Hodges Hall |
|||
| 8:30-9:00
|
Welcoming Remarks
Dr. Duncan Lorimer, Associate Dean for Research, Eberly College of Arts and Sciences Room: 202 Hodges Hall |
|||
| 9:00-10:00
|
Alternating Sign Matrices and Hypermatrices
Richard Brualdi, University of Wisconsin-Madison |
|||
| 10:00-10:20 |
|
|||
|
10:20-10:40
|
|
|||
|
10:40-11:00
|
|
|||
|
11:00-11:20
|
Coffee Break
|
|||
|
11:20-12:20
|
A Solution to the Total Chromatic Number Conjecture
Anthony Hilton University of Reading Cycle Covers of Graphs Dong Ye Middle Tennessee State University |
|||
|
12:20-2:00
|
Lunch Break
|
| Time | Event Title / Speaker / Details | |||
|---|---|---|---|---|
| 2:00-2:20 |
|
|||
| 2:20-2:40
|
|
|||
|
2:40-3:00
|
|
|||
| 3:00-3:20
|
Coffee Break
|
|||
|
3:20-4:20
|
Paths, Cycles, and Edge Coloring
Guantao Chen Georgia State University |
|||
| 4:20-6:00
|
Closing Ceremony
202 Hodges Hall |
|||
| 6:45
|
Dinner: Kome Buffet
|
(chaired by Rong Luo)
Richard A. Brualdi,
University of Wisconsin-Madison
Saturday, April 20, 9:00-10:00, 202 Hodges Hall
From the perspective of combinatorial matrix theory, alternating sign matrices (ASMs) can be considered as generalizations of permutation matrices. We shall give a general introduction to this topic including some recent joint work with Geir Dahl and Michael Schroeder. A generalization to 3-dimensions is also considered. Latin squares can be regarded as 3-dimensional permutation matrices which leads to alternating sign hypermatrices, including the notion of orthogonality.
Guantao Chen,
Georgia State University
Saturday, April 20, 3:20-4:20, 202 Hodges Hall
In this talk, we cover several different topics in structural graph theory with the hope to reveal their connection. We will start a sufficient degree condition for a $k$-connected claw-free graph to have a hamiltonian cycle and the inserting vertices method, several problems on partitioning edges of graphs into cycles and/or paths, and their connection to edge coloring of multigraphs involving some density properties.
Ye Chen,
Northern Arizona University
Saturday, April 20, 10:00-10:20, 210 Hodges Hall
Let $k, r, d$ be positive integers. A $(k, r)$-coloring of a graph $G$ is a proper $k$-vertex coloring of $G$ such that the neighbors of each vertex of degree $d$ will receive at least $\min(d, r)$ different colors. The $r$-hued chromatic number is the smallest integer $k$ for which a graph $G$ has a $(k, r)$-coloring. In this talk, I will introduce the recent developments on the studies related to this $r$-hued coloring and discuss some of the open problems on it.
Joint work with Murong Xu, Suohai Fan, and Hong-Jian Lai.
Chong Li,
Southern Arkansas University
Saturday, April 28, 2:40 - 3:00, 210 Hodges Hall
A triangle-path in a graph $G$ is a sequence of distinct triangles $T_1,T_2,\ldots,T_m$ in $G$ such that for any $i, j$ with $1\leq i < j \leq m$, $|E(T_i)\cap E(T_{i+1})|=1$ and $E(T_i)\cap E(T_j)=\emptyset$ if $j > i+1$. A connected graph $G$ is triangularly connected if for any two nonparallel edges $e$ and $e'$ there is a triangle-path $T_1T_2\cdots T_m$ such that $e\in E(T_1)$ and $e'\in E(T_m)$. For ordinary graphs, Fan et al. characterize all triangularly connected graphs that admit nowhere-zero $3$-flows or $4$-flows. Corollaries of this result include integer flow of some families of ordinary graphs, such as, locally connected graphs due to Lai and some types of products of graphs due to Imrich et al. In this paper, Fan's result for triangularly connected graphs is further extended to signed graphs. We proved that a flow-admissible triangularly connected signed graph admits a nowhere-zero $4$-flow if and only if it is not the wheel $W_5$ associated with a specific signature. Moreover, this result is sharp since there are infinitely many unbalanced triangularly connected signed graphs admitting a nowhere-zero $4$-flow but no $3$-flow.
Elaine Eschen,
West Virginia University
Saturday, April 20, 2:40-3:00, 220 Hodges Hall
We consider a well-known restriction of the graph sandwich problem: Given a graph $G$ with a proper vertex coloring, determine if there is a completion of $G$ (formed by adding edges while maintaining the proper coloring) that has property $P$. We study completions that are bipartite graphs without induced cycles of prescribed lengths. It is known that deciding whether there is a chordal bipartite completion is NP-complete when the input graph is colored with an arbitrary number of colors. We consider the case when the input graph is $3$-colored and show that the problem of deciding whether there is a bipartite completion that avoids induced cycles $C_6, \dots, C_{2p}$, for fixed $p \geq 3$, is NP-complete. We characterize chordal bipartite completions of $3$-colored graphs, and based on this, show that deciding whether a $3$-colored graph can be completed to be chordal bipartite is solvable in $O(m + n\alpha(n))$ time. When a chordal bipartite completion exists, a size-$n$ representation of a completion can be constructed within the same time bound. It follows from our results that for every fixed $k\geq 3$, and for every fixed $p\geq 3$, deciding whether a $k$-colored graph can be completed to be bipartite and $(C_6,\dots, C_{2p})$-free is NP-complete. Also, the corresponding graph sandwich problems are hard.
This is joint work with R Sritharan from University of Dayton.
Anthony Hilton,
University of Reading
Saturday, April 20, 11:00-12:00, 202 Hodges Hall
In 1964 and 1965 Behzad [1] and Vizing [2] independently conjectured that, for a simple graph $G$, $$\chi_T \leq \Delta(G) + 2.$$
In this paper we prove this conjecture.
We actually prove a generalisation of this conjecture. Suppose that to each vertex and each edge there is assigned a paintbox (or list) so that if each paintbox contains $c_T (G)$ coloured paints, then $G$ has a total colouring (i.e. each edge and each vertex gets a colour which is selected from the paintbox for that edge or for that vertex). If all the paintboxes have the same size then the least size for which this is always possible whatever the choice of paintboxes is called the total choice number $c_T (G)$ of $G$. We show that, for a simple graph $G$, $c_T(G) \leq \Delta(G) + 2$. Clearly $\chi_T(G) \leq c_T(G)$.
[1] M. Behzad. Graphs and their chromatic numbers. In Ph.D. Thesis, Michigan State University, 1965.
[2] V.G.Vizing. On an estimate of the chromatic class of a p-graph. In Metody, Diskret. Analiz., Vol. 3, pages 9-17 (in Russian). 1964.
Jianbing Liu,
University of Hartford
Saturday, April 20, 2:20 - 2:40, 220 Hodges Hall
For an integer $k$, a graph $G$ is $k$-matching connected if $G-V(M)$ is a connected nontrivial graph for each matching $M$ with $|M|\leq k-1$, where $V(M)$ is the set of vertices covered by $M$. We show that a graph is $2$-matching connected if and only if either $G\in\{C_4, K_4\}$ or it can be obtained from a $C_4$ by repeatedly applying three graph operations. In addition, for a $k$-matching-connected graph $G$, an edge $e\notin E(G)$ is said to be addible if $G+e$ is still $k$-matching-connected. We prove that every $2$-matching-connected graph $G$ has no addible edge if and only if $G$ is a cycle of length at least $4$. We also show that every $3$-matching-connected graph $G$ with $\delta(G)\geq 5$ has an addible edge, and some examples are given to show that $\delta(G)=5$ is the best possible lower bound. Joint work with Hengzhe Li, Menghan Ma and et al.
Xujun Liu,
Xi'an Jiaotong-Liverpool University
Saturday, April 20, 10:20-10:40, 220 Hodges Hall
For a sequence $(s_1, \ldots, s_k)$ of non-decreasing integers, a packing $S$-coloring of a graph $G$ is a partition of its vertex set $V(G)$ into $V_1, \ldots, V_k$ such that for every pair of distinct vertices $u,v \in V_i$ the distance between $u$ and $v$ is at least $s_i+1$, where $1 \le i \le k$. The packing chromatic number, $\chi_p(G)$, of a graph $G$ is defined to be the smallest integer $k$ such that $G$ has a packing~$(1,2, \ldots, k)$-coloring. Gastineau and Togni asked an open question ``Is it true that the $1$-subdivision ($D(G)$) of any subcubic graph $G$ has packing chromatic number at most $5$?'' and later Bre\v sar, Klav\v zar, Rall, and Wash conjectured that it is true.
In this paper, we prove that every subcubic graph has a packing $(1,1,2,2,3)$-coloring and it is sharp due to the existence of subcubic graphs that are not packing $(1,1,2,2)$-colorable. As a corollary of our result, $\chi_p(D(G)) \le 6$ for every subcubic graph $G$, improving a previous bound ($8$) due to Balogh, Kostochka, and Liu in 2019, and we are now just one step away from fully solving the conjecture. Joint work with Xin Zhang and Yanting Zhang.
Michael Mays,
West Virginia University
Saturday, April 20, 2:20-2:40, 214 Hodges Hall
Integer partitions of $n$ are viewed as bargraphs (i.e., Young diagrams rotated anticlockwise by 90 degrees) in which the $i$th part of the partition $x_i$ is given by the $i$th column of the bargraph with $x_i$ cells. The sun is at infinity in the north west of our two dimensional model and each cell may or may not be lit depending on whether it stands in the shadow cast by another cell to its left. The partition being ordered either as weakly increasing or decreasing yields different generating functions and we consider both cases. We study the number of lit cells in partitions of $n$ in their bargraph representation. In the weakly increasing case the generating function is straightforward, but in the weakly decreasing case we define triangular $q$-binomial coefficients which are analogous to standard $q$-binomial coefficients and we obtain a formula for these. We also study lit nodes in rotated Ferrers diagrams.
Lucian Mazza,
Oakland University
Saturday, April 20, 10:40-11:00, 210 Hodges Hall
Group Coloring is a ``non-homogeneous" generalization of vertex coloring, where vertices are colored with group elements in such a way that adjacent vertices do not differ by a value assigned to the edge they share. This talk will discuss what it means for a group coloring to be unique, as an extension of the previously well-studied unique vertex coloring problem, and present some properties of graphs that can be uniquely colored under some group assignment.
Cheng-Han Pan,
Western New England University
Saturday, April 20, 2:00-2:20, 220 Hodges Hall
This talk is based on our students participation in solving problem 1385 in the Pi Mu Epsilon Journal. We show a closed-form expression of the continued fraction $[1, 1, . . . , 1, 3, 1, 1, . . . , 1]$ and a generalization to $[a, a, . . . , a, b, a, a, . . . , a]$ with a-Fibonacci numbers. In addition, we discuss how much the middle $b$-noise affects the continued fractions with all $a$s.
Pawel Pralat,
Toronto Metropolitan University
Saturday, April 20, 10:00-10:20, 220 Hodges Hall
A $(4, 5)$-coloring of $K_n$ is an edge-coloring of $K_n$ where every $4$-clique
spans at least five colors. We show that there exist $(4, 5)$-colorings of $K_n$
using $\frac 56 n + o(n)$ colors. This settles a disagreement between Erdös and Gyárfás
reported in their 1997 paper. Our construction uses a randomized process which
we analyze using the so-called differential equation method to establish dynamic
concentration. In particular, our coloring process uses random triangle removal,
a process first introduced by Bollobás and Erdös, and analyzed by Bohman, Frieze
and Lubetzky.
(This is a joint work with Bennett, Cushman, and Dudek.)
Yehong Shao,
Ohio University Southern
Saturday, April 20, 2:00-2:20, 214 Hodges Hall
The line graph of a graph $G$, denoted by $L(G)$ or $L^1(G)$, is a simple graph with $E(G)$ being its vertex set, where two vertices in $L(G)$ are adjacent if and only if the corresponding two edges in $G$ have a common vertex. For any integer $n > 0$, the iterated line graphs are recursively defined by $L^n(G)=L(L^{n-1}(G))$ with $L^0(G)=G$. The concept of the Hamiltonian index of a graph $G$ was first introduced by Chartrand as the least nonnegative integer $k$ such that $L^k(G)$ is Hamiltonian. In 1983, Clark and Wormald extended this idea and introduced the Hamiltonian-like indices. Since then there has been a tremendous amount of papers on the indices. We provide a survey on these results and the main techniques applied to prove them.
Joint work with Liming Xiong and Hong-Jian Lai.
Sulin Song,
West Texas A$\&$M University
Saturday, April 20, 10:20 - 10:40, 214 Hodges Hall
Let $r \ge 3$ be an integer. A graph $G$ is $K_{1, r}$-free if $G$ does not have an induced subgraph isomorphic to $K_{1, r}$. A graph $G$ is fully cycle extendable if every vertex in $G$ lies on a cycle of length 3 and every non-hamiltonian cycle in $G$ is extendable. A connected graph $G$ is a split graph if the vertex set of $G$ can be partitioned into a clique and a stable set. Dai et al. in [Discrete Mathematics, 345 (2022), 112826] conjectured that every $(r-1)$-connected $K_{1,r}$-free split graph is hamiltonian, and they proved this conjecture when $r = 4$ while Renjith and Sadagopan proved the case when $r = 3$. In this paper, we introduce a special type of alternating paths in the study of hamiltonian properties of split graphs and prove that a split graph $G$ is hamiltonian if and only if $G$ is fully cycle extendable. Consequently, for $r\in\{3,4\}$, every $r$-connected $K_{1,r}$-free split graph is Hamilton-connect and every $(r-1)$-connected $K_{1,r}$-free split graph is fully cycle extendable. Joint work with Xia Liu, Mingquan Zhan and Hong-Jian Lai.
Zi-Xia Song,
University of Central Florida
Saturday, April 20, 10:40 - 11:00, 220 Hodges Hall
For integers $k>\ell\ge0$, a graph $G$ is $(k,\ell)$-stable if $\alpha(G-S)\geq \alpha(G)-\ell$ for every $S\subseteq V(G)$ with $|S|=k$. A recent result of Dong and Wu [SIAM J. Discrete Math. 36 (2022) 229--240] shows that every $(k,\ell)$-stable graph $G$ satisfies $\alpha(G) \le \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$. A $(k,\ell)$-stable graph $G$ is tight if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$; and $q$-tight for some integer $q\ge0$ if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell-q$. In this talk, we first prove that for all $k\geq 24$, the only tight $(k, 0)$-stable graphs are $K_{k+1}$ and $K_{k+2}$, answering a question of Dong and Luo [arXiv: 2401.16639]. We then prove that for all nonnegative integers $k, \ell, q$ with $k\geq 3\ell+3$, every $q$-tight $(k,\ell)$-stable graph has at most $k-3\ell-3+2^{3(\ell+2q+4)^2}$ vertices, answering a question of Dong and Luo in the negative.
This is joint work with Xiaonan Liu and Zhiyu Wang.
Maya Tennant,
Virginia Commonwealth University
Saturday, April 20, 2:20-2:40, 210 Hodges Hall
Here we introduce a game on graphs, called cup stacking, following a line of what can be considered as $0$-, $1$-, or $2$-person games such as chip firing, percolation, graph burning, zero forcing, cops and robbers, graph pebbling, and graph pegging, among others. It can be more general, but the most basic scenario begins with a single cup on each vertex of a graph. For a vertex with $k$ cups on it we can move all its cups to a vertex at distance $k$ from it, provided the second vertex already has at least one cup on it. The object is to stack all cups onto some pre-described target vertex. We say that a graph is stackable if this can be accomplished for all possible target vertices. This game has been explored in some of these basic configurations as frog jumping on graphs.
In this paper we study cup stacking on many families of graphs, developing a characterization of stackability in graphs and using it to prove the stackability of complete graphs, paths, cycles, grids, the Petersen graph, many Kneser graphs, some trees, cubes of dimension up to 20, ``somewhat balanced'' complete $t$-partite graphs, and Hamiltonian diameter two graphs. Additionally we use the Gallai-Edmonds Structure Theorem, the Edmonds Blossom Algorithm, and the Hungarian algorithm to devise a polynomial algorithm to decide if a diameter two graph is stackable.
Our proof that cubes up to dimension 20 are stackable uses Kleitman's Symmetric Chain Decomposition and the new result of Merino, M\"utze, and Namrata that all generalized Johnson graphs (excluding the Petersen graph) are Hamiltonian. We conjecture that all cubes and higher-dimensional grids are stackable, and leave the reader with several open problems, questions, and generalizations.
Joint work with Paul Fay and Glenn Hurlbert.
Lin Tian,
Middle Tennessee State University
Saturday, April 20, 2:40 - 3:00, 214 Hodges Hall
In 1981, C. Thomassen proved that every $(k+3)$-connected graph $G$ contains a cycle $C$ such that $\kappa(G-V(C))\ge k$. Further, he proved that every $(s+t-1)$-connected graph $G$ of minimum degree at least $g(n(s),n(t))$, its vertex set can be decomposed into two sets $S$ and $T$ such that the subgraphs $G[S]$ and $G[T]$ have connectivity at least $s$ and $t$, respectively. In this paper, we prove that every $(k+1)$-connected graph with minimum degree at least $\frac{3k}{2}+2m-3$ contains a cycle of length at least $m$ whose removal remains $k$-connected. Our proof leads to a polynomial algorithm for finding a such long cycle in $(k+1)$-connected graphs.
Murong Xu,
University of Scranton
Saturday, April 20, 10:20-10:40, 210 Hodges Hall
Let $k, r, d$ be positive integers. A $(k, r)$-coloring of a graph $G$ is a proper
$k$-vertex coloring of $G$ such that the neighbors of each vertex of degree $d$
will receive at least $\min(d, r)$ different colors. The $r$-hued chromatic number
is the smallest integer $k$ for which a graph $G$ has a $(k, r)$-coloring. In this
talk, I will introduce the recent developments on the studies related to this $r$-hued
coloring and discuss some of the open problems on it.
Joint work with Ye Chen, Suohai Fan, and Hong-Jian Lai.
Dong Ye,
Middle Tennessee State University
Saturday, April 20, 11:00 - 12:00, 202 Hodges Hall
Let $G$ be a graph. A cycle cover of a graph $G$ is a family of cycles which contain every edge of $G$. A cycle double cover is a family of cycles such that every edge is contained by exactly two cycles in the family. The well-known cycle double cover conjecture, due to Seymour and Szekeres, asserts that every bridgeless graph has a cycle double cover. In this talk, we will focus on some old and new results on cycle covers of graphs.
Gexin Yu,
College of William and Mary
Saturday, April 20, 2:00 - 2:20, 210 Hodges Hall
An induced matching in a graph $G$ is a matching such that its end vertices also induce a matching. A $(1^{\ell}, 2^k)$-packing edge-coloring of a graph $G$ is a partition of its edge set into disjoint unions of $\ell$ matchings and $k$ induced matchings. Gastineau and Togni (2019), as well as Hocquard, Lajou, and Lu\v zar (2022), have conjectured that every subcubic graph is $(1^2,2^4)$-packing edge-colorable. In this paper, we confirm that their conjecture is true (for connected subcubic graphs with more than $70$ vertices). Our result is sharp due to the existence of subcubic graphs that are not $(1^2,2^3)$-packing edge-colorable. This is joint work with Xujun Liu.
Mingquan Zhan,
Millersville University of Pennsylvania
Saturday, April 20, 10:00-10:20, 214 Hodges Hall
A graph $G$ is pancyclic if it contains cycles of all possible lengths. %A graph $G$ is 1-hamiltonian if the removal of at most 1 vertices from $G$ results in a hamiltonian graph. In [J. Graph Theory, 12 (1988) 413-420] Veldman showed that the line graph $L(G)$ of a connected graph $G$ with diameter at most 2 is hamiltonian. In this paper, we continue studying the line graph $L(G)$ of a connected graph $G$ with $|E(G)|\ge 3$ and diameter at most 2 and prove that $L(G)$ is pancyclic if and only if $G$ is not a cycle of length 4 or 5, and $G$ is not the Petersen graph. This is a joint work with Drs. Xiaoling Ma, Lan Lei, and Hong-Jian Lai.
Ju Zhou,
Kutztown University of Pennsylvania
Saturday, April 20, 10:40 - 11:00, 214 Hodges Hall
Given a finite simple graph $G$, a set $D \subset V (G)$ is said to be a dominating set if for all $v \in V(G)$, either $v\in D$ or $v$ is adjacent to some vertex in $D$. For a graph $G$, the domination number is the size of the smallest possible dominating set. If $D$ is a dominating set of $G$ such that $|D|$ equals the domination number of $G$, then $D$ is called a minimum dominating set. Furthermore, $D$ is called a unique minimum dominating set if there is precisely one minimum dominating set $D$. Given a graph $G$, a dominating set $D$ is an independent dominating set if none of the vertices in $D$ are adjacent. If each vertex not in $D$ is adjacent to precisely one element in $D$, then $D$ is a perfect dominating set. If $D$ is both independent and perfect, it is an efficient dominating set. In this paper, the authors discussed some properties of efficient dominating sets and then investigated several family graphs about whether they have efficient dominating sets.