Browsing by Author "Weng, Chih-wen"

Now showing 1 - 16 of 16

3-bounded property in a triangle-free distance-regular graph
(2008-10-01)
Pan, Yeh-jong
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let Gamma denote a distance-regular graph with classical parameters (D, b, alpha, beta) and D >= 3. Assume the intersection numbers a(1) = 0 and a(2) not equal 0. We show that Gamma is 3-bounded in the sense of the article [C. Weng, D-bounded distance-regular graphs, European Journal of Combinatorics 18 (1997) 211-229]. (c) 2007 Elsevier Ltd. All rights reserved.
A bound on the Laplacian spread which is tight for strongly regular graphs
(2015-04-01)
Lin, Fan-Hsuan
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
The Laplacian spread of a graph is the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. For Laplacian matrices of graphs, we find their upper bounds of largest eigenvalues, lower bounds of second-smallest eigenvalues and upper bounds of Laplacian spreads. The strongly regular graphs attain all the above bounds. Some other extremal graphs are also provided. (C) 2015 Elsevier Inc. All rights reserved.
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 characterization of strongly regular graphs in terms of the largest signless Laplacian eigenvalues
(2016-10-01)
Fan, Feng-lei
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let G be a simple graph of order n with maximum degree Delta. Let lambda (resp. mu) denote the maximum number of common neighbors of a pair of adjacent vertices (resp. nonadjacent distinct vertices) of G. Let q(G) denote the largest eigenvalue of the signless Laplacian matrix of G. We show that q(G) <= Delta - mu/4 + root(Delta - mu/4)(2) + (1 + lambda)Delta + mu(n - 1) -Delta(2), with equality if and only if G is a strongly regular graph with parameters (n, Delta, lambda, mu). (C) 2016 Elsevier Inc. All rights
A note on triangle-free distance-regular graphs with a(2) not equal 0
(2009-01-01)
Pan, Yeh-jong
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let Gamma denote a distance-regular graph with classical parameters (D, b, alpha, beta) and D >= 3. Assume the intersection numbers a(1) = 0 and a(2) not equal 0. We show that the intersection number c(2) is either 1 or 2, and if c(2) = 1, then (b, alpha, beta) = (-2, -2, ((-2)(D+l) - 1)/3). (C) 2008 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 Extending Result on Spectral Radius of Bipartite Graphs
(2018-04-01)
Cheng, Yen-Jen
;
Fan, Feng-lei
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
In this paper, we study the spectral radius of bipartite graphs. Let G be a bipartite graph with e edges without isolated vertices. It was known that the spectral radius of G is at most the square root of e, and the upper bound is attained if and only if G is a complete bipartite graph. Suppose that G is not a complete bipartite graph and (e - 1, e + 1) is not a pair of twin primes. We describe the maximal spectral radius of G. As a byproduct of our study, we obtain a spectral characterization of a pair (e - 1, e + 1) of integers to be a pair of twin primes.
More on pooling spaces
(2008-12-28)
Huang, Hau-wen
;
Huang, Yu-pei
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
A pooling space is a ranked poset P such that the subposet w(+) induced by the elements above w is atomic for each element w of P. Pooling spaces were introduced in IT. Huang, C. Weng, Pooling spaces and non-adaptive pooling designs, Discrete Math. 282 (2004) 163-169] for the purpose of giving a uniform way to construct pooling designs, which have applications to the screening of DNA sequences. Many examples of pooling spaces were given in that paper. In this paper, we clarify a few things about the definition of pooling spaces. Then we find that a geometric lattice, a well-studied structure in literature, is also a pooling space. This provides us many classes of pooling designs, some old and some new. We study the pooling designs constructed from affine geometries. We find that some of them meet the optimal bounds related to a conjecture of Erdos, Frankl and Furedi. (c) 2007 Elsevier B.V. All rights reserved.
Nonexistence of a Class of Distance-regular Graphs
(2015-06-03)
Huang, Yu-pei
;
Pan, Yeh-jong
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let Gamma denote a distance-regular graph with diameter D >= 3 and intersection numbers a(1) = 0, a(2) not equal 0, and c(2) = 1. We show a connection between the d-bounded property and the nonexistence of parallelograms of any length up to d + 1. Assume further that Gamma is with classical parameters (D, b, alpha, beta), Pan and Weng (2009) showed that (b, alpha, beta) = (-2, 2, ((-2)(D+1) -1)/3). Under the assumption D >= 4, we exclude this class of graphs by an application of the above connection.
Pooling semilattices and non-adaptive pooling designs
(2014-04-06)
Guo, Jun
;
Wang, Kaishun
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
In Huang and Weng (2004), Huang and Weng introduced pooling spaces, and constructed pooling designs from a pooling space. In this paper, we introduce the concept of pooling semilattices and prove that a pooling semilattice is a pooling space, then show how to construct pooling designs from a pooling semilattice. Moreover, we give many examples of pooling semilattices and thus obtain the corresponding pooling designs. (C) 2013 Elsevier B.V. All rights reserved.
Pooling spaces associated with finite geometry
(2008-08-01)
Huang, Tayuan
;
Wang, Kaishun
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Motivated by the works of Ngo and Du [H. Ngo, D. Du, A survey on combinatorial group testing algorithms with applications to DNA library screening, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 55 (2000) 171-182], the notion of pooling spaces was introduced IT. Huang, C. Weng, Pooling spaces and non-adaptive pooling designs, Discrete Mathematics 282 (2004) 163-169] for a systematic way of constructing pooling designs; note that geometric lattices are among pooling spaces. This paper attempts to draw possible connections from finite geometry and distance regular graphs to pooling spaces: including the projective spaces, the affine spaces, the attenuated spaces, and a few families of geometric lattices associated with the orbits of subspaces under finite classical groups, and associated with d-bounded distance-regular graphs. (C) 2007 Elsevier Ltd. All rights reserved.
Spectral radius and degree sequence of a graph
(2013-04-15)
Liu, Chia-an
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let G be a simple connected graph of order n with degree sequence d(1), d(2), ... , dr, in non-increasing, order. The spectral radius rho(G) of G is the largest eigenvalue of its adjacency matrix. For each positive integer l at most n, we give a sharp upper bound for rho(G) by a function of d(1), d(2), ... ,d(l), which generalizes a series of previous results. (C) 2013 Elsevier Inc. All rights reserved.
Spectral radius of bipartite graphs
(2015-06-01)
Liu, Chia-an
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let k, p, q be positive integers with k < p < q + 1. We prove that the maximum spectral radius of a simple bipartite graph obtained from the complete bipartite graph K-p,K-q of bipartition orders p and q by deleting k edges is attained when the deleted edges are all incident on a common vertex which is located in the partite set of order q. Our method is based on new sharp upper bounds on the spectral radius of bipartite graphs in terms of their degree sequences. (C) 2015 Elsevier Inc. All rights reserved.
The edge-flipping group of a graph
(2010-04-01)
Huang, Hau-wen
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let X = (V, E) be a finite simple connected graph with it vertices and In edges A configuration is all assignment of one of the two colors, black or white, to each edge of X. A move applied to a configuration is to select a black edge c c E and change the colors of all adjacent edges off Given all Initial Configuration and a filial Configuration, try to find a sequence of moves that transforms the Initial Configuration into the final configuration This is rile edge-flipping puzzle oil X, and it corresponds to a group action This group is called the edge-flipping group W(E)(X) of X This paper shows that if X has at least three vertices. W(r)(X) is isomorphic to a semidirect product of (Z/2Z)(k) and the symmetric group S(n) of degree n, where k = (n - 1)(m - n + 1) if n is odd, k = (n - 2)(m - n + 1) if n is even, and Z is the additive group of integers (C) 2009 Elsevier Ltd All rights reserved.
The flipping puzzle on a graph
(2010-08-01)
Huang, Hau-wen
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let S be a connected graph which contains an induced path of n - 1 vertices, where n is the order of S. We consider a puzzle on S. A configuration of the puzzle is simply an n-dimensional column vector over {0, 1} with coordinates of the vector indexed by the vertex set S. For each configuration u with a coordinate u(s) = 1, there exists a move that sends u to the new configuration which flips the entries of the coordinates adjacent to s in u. We completely determine if one configuration can move to another in a sequence of finite steps. (C) 2010 Published by Elsevier Ltd
Triangle-free distance-regular graphs
(2008-02-01)
Pan, Yeh-jong
;
Lu, Min-hsin
;
Weng, Chih-wen
;
應用數學系
;
Department of Applied Mathematics
Let Gamma denote a distance-regular graph with diameter d >= 3. By a parallelogram of length 3, we mean a 4-tuple xyzw consisting of vertices of Gamma such that partial derivative(x,y)=partial derivative(z,w)=1, partial derivative(x,z)=3, and partial derivative(x,w)=partial derivative(y,w)=partial derivative(y,z)=2, where partial derivative denotes the path-length distance function. Assume that Gamma has intersection numbers a(1)=0 and a(2)not equal 0. We prove that the following (i) and (ii) are equivalent. (i) Gamma is Q-polynomial and contains no parallelograms of length 3; (ii) Gamma has classical parameters (d,b,alpha,beta) with b <-1. Furthermore, suppose that (i) and (ii) hold. We show that each of b(b+1)(2)(b+2)/c (2), (b-2)(b-1)b(b+1)/(2+2b-c (2)) is an integer and that c (2)<= b(b+1). This upper bound for c (2) is optimal, since the Hermitian forms graph Her(2)(d) is a triangle-free distance-regular graph that satisfies c (2)=b(b+1).