Qinghong Zhao

dblp:270/1307 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2023
0000-0002-2813-9413ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2023 Bonds Intersecting Long Paths in \(k\) -Connected Graphs
abstract
Abstract. In 1966, Gallai asked whether there is a vertex which passes through all longest paths of a connected graph. Although this has been verified for some special classes of graphs such as outerplanar graphs, circular arc graphs, and series-parallel graphs, the answer is negative for general graphs. In this paper, we prove among other results that if we replace the vertex by a bond, then the answer is affirmative. A bond of a graph is a minimal nonempty edge-cut. In particular, in any 2-connected graph, the set of all edges incident to a vertex is a bond, called a vertex-bond. Clearly, for a 2-connected graph, a path passes through a vertex [Formula: see text] if and only if it meets the vertex-bond with respect to [Formula: see text]. Therefore, a very natural approach to Gallai’s question is to study whether there is a bond meeting all longest paths. Let [Formula: see text] denote the length of a longest path of connected graphs. We show that there is a bond meeting all paths of length at least [Formula: see text] and [Formula: see text] for any 2- and 3-connected graph, respectively. For any [Formula: see text]-connected graph [Formula: see text], we show that there is a bond meeting all paths of length at least [Formula: see text], where [Formula: see text] if [Formula: see text] is even and [Formula: see text] if [Formula: see text] is odd. Our results also provide analogs of the results on bonds meeting long cycles given in [P.-L. Wu, Combin. Probab. Comput., 6 (1997), pp. 107–113; and S. McGuinness, Combinatorica, 25 (2005), pp. 439–450].
Qinghong Zhao, Bing Wei 0001, Haidong Wu
SIAM J. Discret. Math.1
2021 Gallai-Ramsey numbers for graphs with chromatic number three
Qinghong Zhao, Bing Wei 0001
Discret. Appl. Math.1