Bing Wei 0001

dblp:58/1390-1 · DBLP profile ↗
← Back
7ranked-venue papers
0as first author
2since 2021 · last 2023
0000-0002-6932-0251ORCID · verified

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

Theory of computation · 7 · 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.2
2021 Gallai-Ramsey numbers for graphs with chromatic number three
Qinghong Zhao, Bing Wei 0001
Discret. Appl. Math.2
2015 Multiplicative Zagreb indices of k-trees
Shaohui Wang, Bing Wei 0001
Discret. Appl. Math.2
2012 Independence polynomials of some compound graphs
Lanzhen Song, William Staton, Bing Wei 0001
Discret. Appl. Math.3
2010 Independence polynomials of k-tree related graphs
Lanzhen Song, William Staton, Bing Wei 0001
Discret. Appl. Math.3
2001 A degree condition of 2-factors in bipartite graphs
Xiangwen Li, Bing Wei 0001, Fan Yang 0074
Discret. Appl. Math.2
1999 Hamiltonicity in 3-domination-critical Graphs with alpha = delta + 2
Feng Tian 0008, Bing Wei 0001, Lei Zhang 0030
Discret. Appl. Math.2