Browsing by Author "Lee, Guang-Siang"

Now showing 1 - 3 of 3

A characterization of bipartite distance-regular graphs
(2014-04-01)
Lee, Guang-Siang
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
It is well-known that the halved graphs of a bipartite distanceregular graph are distance-regular. Examples are given to show that the converse does not hold. Thus, a natural question is to find out when the converse is true. In this paper we give a quasi-spectral characterization of a connected bipartite weighted 2-punctually distance-regular graph whose halved graphs are distance-regular. In the case the spectral diameter is even we show that the graph characterized above is distanceregular. (C) 2013 Elsevier Inc. All rights reserved.
A spectral excess theorem for nonregular graphs
(2012-10-01)
Lee, Guang-Siang
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
The spectral excess theorem asserts that the average excess is, at most, the spectral excess in a regular graph, and equality holds if and only if the graph is distance-regular. An example demonstrates that this theorem cannot directly apply to nonregular graphs. This paper defines average weighted excess and generalized spectral excess as generalizations of average excess and spectral excess, respectively, in nonregular graphs, and proves that for any graph the average weighted excess is at most the generalized spectral excess. Aside from distance-regular graphs, additional graphs obtain the new equality. We show that a graph is distance-regular if and only if the new equality holds and the diameter D equals the spectral diameter d. For application, we demonstrate that a graph with odd-girth 2d + 1 must be distance-regular, generalizing a recent result of van Dam and Haemers. (C) 2012 Elsevier Inc. All rights reserved.
An extension of Stein-Lovasz theorem and some of its applications
(2013-01-01)
Lee, Guang-Siang
;
應用數學系
;
Department of Applied Mathematics
The Stein-Lovasz theorem provides an algorithmic way to deal with the existence of certain good coverings, and thus offers bounds related to some combinatorial structures. An extension of the classical Stein-Lovasz theorem for multiple coverings is given, followed by some applications for finding upper bounds of the sizes of (d,s out of r;z]-disjunct matrices and (k,m,c,n;z)-selectors, respectively. This gives a unified treatment for some previously known results relating to various models of group testing.