ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Thu, 01 Dec 2022 07:07:11 GMT2022-12-01T07:07:11Z50241- Maximum multiplicity of matching polynomial roots and minimum path cover in general graphshttps://scholarbank.nus.edu.sg/handle/10635/103537Title: Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
Authors: Ku, C.Y.; Wong, K.B.
Abstract: Let G be a graph. It is well known that the maximum multiplicity of a root of the matching polynomial μ(G, x) is at most the minimum number of vertex disjoint paths needed to cover the vertex set of G. Recently, a necessary and sufficient condition for which this bound is tight was found for trees. In this paper, a similar structural characterization is proved for any graph. To accomplish this, we extend the notion of a (Θ,G)-extremal path cover (where Θ is a root of μ(G, x)) which was first introduced for trees to general graphs. Our proof makes use of the analogue of the Gallai-Edmonds Structure Theorem for general root. By way of contrast, we also show that the difference between the minimum size of a path cover and the maximum multiplicity of matching polynomial roots can be arbitrarily large.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1035372011-01-01T00:00:00Z
- Maximum multiplicity of a root of the matching polynomial of a tree and minimum path coverhttps://scholarbank.nus.edu.sg/handle/10635/103536Title: Maximum multiplicity of a root of the matching polynomial of a tree and minimum path cover
Authors: Ku, C.Y.; Wong, K.B.
Abstract: We give a necessary and suffcient condition for the maximum multiplicity of a root of the matching polynomial of a tree to be equal to the minimum number of vertex disjoint paths needed to cover it.
Sat, 07 Feb 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1035362009-02-07T00:00:00Z
- A generalization of very odd sequenceshttps://scholarbank.nus.edu.sg/handle/10635/128029Title: A generalization of very odd sequences
Authors: Ku, Cheng Yeaw; Wong, Kok Bin
Thu, 01 Jan 2015 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1280292015-01-01T00:00:00Z
- A Deza-Frankl type theorem for set partitionshttps://scholarbank.nus.edu.sg/handle/10635/128030Title: A Deza-Frankl type theorem for set partitions
Authors: Ku, Cheng Yeaw; Wong, Kok Bin
Thu, 01 Jan 2015 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1280302015-01-01T00:00:00Z
- Cayley graph on symmetric group generated by elements fixing k pointshttps://scholarbank.nus.edu.sg/handle/10635/123535Title: Cayley graph on symmetric group generated by elements fixing k points
Authors: Ku C.Y.; Wong K.B.
Thu, 01 Jan 2015 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1235352015-01-01T00:00:00Z
- On r-cross intersecting families of setshttps://scholarbank.nus.edu.sg/handle/10635/103749Title: On r-cross intersecting families of sets
Authors: Ku, C.Y.; Wong, K.B.
Abstract: Let [n] = {1,..., n} and denote the family of all k-subsets of [n]. For i = 1, 2,..., r, let Fi⊆. Suppose that F1∩··· ∩Fr≠∅ holds for all Fi∈Fi. We show that ki≤n/2 for all i, then Moreover, equality holds if and only if there is an element x ∈ [n] such that for all i. © 2013 Pushpa Publishing House.
Mon, 01 Apr 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1037492013-04-01T00:00:00Z
- On cross-intersecting families of set partitionshttps://scholarbank.nus.edu.sg/handle/10635/103697Title: On cross-intersecting families of set partitions
Authors: Ku, C.Y.; Wong, K.B.
Abstract: Let B(n) denote the collection of all set partitions of [n]. Suppose A1, A2 ⊆ B(n) are cross-intersecting i.e. for all A1 ∈ A1 and A2 ∈ A2, we have A1 ∩ A2 ≠ {circled division slash}. It is proved that for sufficiently large n, |A1| |A2| ≤ B2 n-1 where Bn is the n-th Bell number. Moreover, equality holds if and only if A1 = A2 and A1 consists of all set partitions with a fixed singleton.
Mon, 31 Dec 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1036972012-12-31T00:00:00Z
- On r-regular subgraphs with hamiltonian cycles in graphs with many edgeshttps://scholarbank.nus.edu.sg/handle/10635/126637Title: On r-regular subgraphs with hamiltonian cycles in graphs with many edges
Authors: Yeaw Ku, C.; Bin Wong, K.
Abstract: In this paper, we prove that for 0 < β < 1 (2r + 1) and sufficiently large n, every graph G with n vertices and at least n2-β edges contains a subgraph G′ with at least n2-2β 26 edges, such that any t disjoint edges in G' lie together on an r-regular subgraph with at most 2rt vertices. Furthermore, the r-regular subgraph has a Hamiltonian cycle that contains all the t disjoint edges. © 2014 Pushpa Publishing House, Allahabad, India.
Wed, 01 Jan 2014 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1266372014-01-01T00:00:00Z
- Properties of θ-super positive graphshttps://scholarbank.nus.edu.sg/handle/10635/103981Title: Properties of θ-super positive graphs
Authors: Ku, C.Y.; Wong, K.B.
Abstract: Let the matching polynomial of a graph G be denoted by μ(G; x). A graph G is said to be θ-super positive if μ(G; θ) ≠ 0 and μ(G \ n v;θ) = 0 for all v ∈ V (G). In particular, G is 0-super positive if and only if G has a perfect matching. While much is known about 0-super positive graphs, almost nothing is known about θ-super positive graphs for θ ≠ 0. This motivates us to investigate the structure of θ-super positive graphs in this paper. Though a 0-super positive graph need not contain any cycle, we show that a θ-super positive graph with θ 6≠ 0 must contain a cycle. We introduce two important types of θ-super positive graphs, namely θ-elementary and θ-base graphs. One of our main results is that any θ-super positivegraph G can be constructed by adding certain type of edges to a disjoint union of θ-base graphs; moreover, these θ-base graphs are uniquely determined by G. We also give a characterization of θ-elementary graphs: a graph G is θ-elementary if and only if the set of all its θ-barrier sets form a partition of V (G). Here, θ-elementary graphs and θ-barrier sets can be regarded as θ-analogue of elementary graphs and Tutte sets in classical matching theory.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1039812012-01-01T00:00:00Z
- Eigenvalues of the derangement graphhttps://scholarbank.nus.edu.sg/handle/10635/103193Title: Eigenvalues of the derangement graph
Authors: Ku, C.Y.; Wales, D.B.
Abstract: We consider the Cayley graph on the symmetric group Sn generated by derangements. It is well known that the eigenvalues of this graph are indexed by partitions of n. We investigate how these eigenvalues are determined by the shape of their corresponding partitions. In particular, we show that the sign of an eigenvalue is the parity of the number of cells below the first row of the corresponding Ferrers diagram. We also provide some lower and upper bounds for the absolute values of these eigenvalues. © 2009 Elsevier Inc. All rights reserved.
Thu, 01 Apr 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1031932010-04-01T00:00:00Z
- Extensions of barrier sets to nonzero roots of the matching polynomialhttps://scholarbank.nus.edu.sg/handle/10635/103259Title: Extensions of barrier sets to nonzero roots of the matching polynomial
Authors: Ku, C.Y.; Wong, K.B.
Abstract: In matching theory, barrier sets (also known as Tutte sets) have been studied extensively due to their connection to maximum matchings in a graph. For a root θ of the matching polynomial, we define θ-barrier and θ-extreme sets. We prove a generalized BergeTutte formula and give a characterization for the set of all θ-special vertices in a graph. © 2010 Elsevier B.V. All rights reserved.
Tue, 28 Dec 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1032592010-12-28T00:00:00Z
- An analogue of the Hilton-Milner theorem for set partitionshttps://scholarbank.nus.edu.sg/handle/10635/102816Title: An analogue of the Hilton-Milner theorem for set partitions
Authors: Ku, C.Y.; Wong, K.B.
Abstract: Let B(n) denote the collection of all set partitions of [n]. Suppose A⊆B(n) is a non-trivial t-intersecting family of set partitions i.e. any two members of A have at least t blocks in common, but there is no fixed set of t blocks of size one which belong to all of them. It is proved that for sufficiently large n depending on t,|A|≤Bn-t-B~n-t-B~n-t-1+t where B n is the n-th Bell number and B~n is the number of set partitions of [n] without blocks of size one. Moreover, equality holds if and only if A is equivalent to{P∈B(n):{1},{2},...,{t},{i}∈Pfor somei∉{1,2,...,t,n}}∪{Q(i,n):1≤i≤t} where Q(i, n) = {{i, n}} ∪ {{j} : j ∈ [n] {set minus} {i, n}}. This is an analogue of the Hilton-Milner theorem for set partitions. © 2013 Elsevier Inc.
Sun, 01 Sep 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028162013-09-01T00:00:00Z
- Gallai-Edmonds structure theorem for weighted matching polynomialhttps://scholarbank.nus.edu.sg/handle/10635/103315Title: Gallai-Edmonds structure theorem for weighted matching polynomial
Authors: Ku, C.Y.; Wong, K.B.
Abstract: In this paper, we prove the Gallai-Edmonds structure theorem for weighted matching polynomials. Our result implies the Parter-Wiener theorem and its recent generalization about the existence of principal submatrices of a Hermitian matrix whose graph is a tree. © 2013 Elsevier Inc.
Sun, 01 Dec 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1033152013-12-01T00:00:00Z
- An analogue of the hilton-milner theorem for weak compositionshttps://scholarbank.nus.edu.sg/handle/10635/127298Title: An analogue of the hilton-milner theorem for weak compositions
Authors: Ku, Cheng Yeaw; Wong, Kokbin
Thu, 01 Jan 2015 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1272982015-01-01T00:00:00Z
- Generalizing Tutte's theorem and maximal non-matchable graphshttps://scholarbank.nus.edu.sg/handle/10635/103336Title: Generalizing Tutte's theorem and maximal non-matchable graphs
Authors: Ku, C.Y.; Wong, K.B.
Abstract: A graph G has a perfect matching if and only if 0 is not a root of its matching polynomial μ(G, x). Thus, Tutte's famous theorem asserts that 0 is not a root of μ(G, x) if and only if codd(G - S) ≤ |S| for all S ⊆ V(G), where codd(G) denotes the number of odd components of G. Tutte's theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte's theorem in terms of avoiding any given real number Θ as a root of μ(G, x). We also extend maximal nonmatchable graphs to maximal Θ-non-matchable graphs and determine the structure of such graphs. © 2013 Elsevier B.V. All rights reserved.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1033362013-01-01T00:00:00Z
- On 2-factor hamiltonian regular bipartite graphshttps://scholarbank.nus.edu.sg/handle/10635/103666Title: On 2-factor hamiltonian regular bipartite graphs
Authors: Ku, C.Y.; Wong, K.B.
Abstract: A k-regular bipartite graph is said to be 2-factor hamiltonian if each of its 2-factor is hamiltonian. It is well known that if a k-regular bipartite graph is 2-factor hamiltonian, then k≦3. In this paper, we give a new proof of this fact. © 2012 Akadémiai Kiadó, Budapest, Hungary.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1036662013-01-01T00:00:00Z
- A Kruskal-Katona type theorem for integer partitionshttps://scholarbank.nus.edu.sg/handle/10635/102664Title: A Kruskal-Katona type theorem for integer partitions
Authors: Ku, C.Y.; Wong, K.B.
Abstract: Let N be the set of positive integers, and let P(n) {equation presented} be the set of (ordered) partitions of n. We show that there exist a rank function and orderings ≤c and such that the ranked poset (P(n),≤c) is Macaulay. © 2013 Elsevier B.V. All rights reserved.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026642013-01-01T00:00:00Z
- Independent sets of maximal size in tensor powers of vertex-transitive graphshttps://scholarbank.nus.edu.sg/handle/10635/103414Title: Independent sets of maximal size in tensor powers of vertex-transitive graphs
Authors: Ku, C.Y.; McMillan, B.B.
Abstract: Let G be a connected, nonbipartite vertex-transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product G×G are the preimages of the independent sets of maximal cardinality inGunder projections, then the same holds for all finite tensor powers of G, thus providing an affirmative answer to a question raised by Larose and Tardif (J Graph Theory 40(3) (2002), 162-171).© 2009 Wiley Periodicals, Inc.
Wed, 01 Apr 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1034142009-04-01T00:00:00Z
- Generalized D-graphs for nonzero roots of the matching polynomialhttps://scholarbank.nus.edu.sg/handle/10635/103327Title: Generalized D-graphs for nonzero roots of the matching polynomial
Authors: Ku, C.Y.; Wong, K.B.
Abstract: Recently, Bauer et al. [D. Bauer, H.J. Broersma, A. Morgana, E. Schmeichel, Tutte sets in graphs I: maximal Tutte sets and D-graphs, J. Graph Theory 55 (2007) 343358] introduced a graph operator D(G), called the D-graph of G, which has been useful in investigating the structural aspects of maximal Tutte sets in G with a perfect matching. Among other results, they proved a characterization of maximal Tutte sets in terms of maximal independent sets in the graph D(G) and maximal extreme sets in G. This was later extended to graphs without perfect matchings by Busch et al. [A. Busch, M. Ferrara, N. Kahl, Generalizing D-graphs, Discrete Appl. Math. 155 (2007) 24872495]. Let θ be a real number and μ(G,x) be the matching polynomial of a graph G. Let mult(θ,G) be the multiplicity of θ as a root of μ(G,x). We observe that the notion of D-graph is implicitly related to θ=0. In this paper, we give a natural generalization of the D-graph of G for any real number θ, and denote this new operator by Dθ(G), so that Dθ(G) coincides with D(G) when θ=0. We prove a characterization of maximal θ-Tutte sets which are θ-analogues of maximal Tutte sets in G. In particular, we show that for any X⊆V(G), |X|>1, and any real number θ, mult(θ,G\X)=mult(θ,G)+|X| if and only if mult(θ,G\uv)= mult(θ,G)+2 for any u,v∈X, u≠v, thus extending the preceding work of Bauer et al. (2007) [2] and Busch et al. (2007) [3] which established the result for the case θ=0. Subsequently, we show that every maximal θ-Tutte set X is matchable to an independent set Y in G; moreover, Dθ(G) always contains an isomorphic copy of the subgraph induced by X∪Y. To this end, we introduce another related graph Sθ(G) which is a supergraph of G, and prove that Sθ(G) and G have the same GallaiEdmonds decomposition with respect to θ. Moreover, we determine the structure of Dθ(G) in terms of its GallaiEdmonds decomposition and prove that Dθ( Sθ(G))= Dθ(G). © 2011 Elsevier B.V. All rights reserved.
Fri, 28 Oct 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1033272011-10-28T00:00:00Z
- On r-cross t-intersecting families for weak compositionshttps://scholarbank.nus.edu.sg/handle/10635/128014Title: On r-cross t-intersecting families for weak compositions
Authors: Ku, Cheng Yeaw; Wong, Kok Bin
Thu, 01 Jan 2015 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1280142015-01-01T00:00:00Z
- The covering radius problem for sets of 1-factors of the complete uniform hypergraphshttps://scholarbank.nus.edu.sg/handle/10635/128015Title: The covering radius problem for sets of 1-factors of the complete uniform hypergraphs
Authors: Aw, Alan J.; Ku, Cheng Yeaw
Thu, 01 Jan 2015 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1280152015-01-01T00:00:00Z
- An analogue of the Erdos-Ko-Rado theorem for weak compositionshttps://scholarbank.nus.edu.sg/handle/10635/102814Title: An analogue of the Erdos-Ko-Rado theorem for weak compositions
Authors: Ku, C.Y.; Wong, K.B.
Abstract: Let n0 be the set of non-negative integers, and let P(n,l) denote the set of all weak compositions of n with l parts, i.e., P(n,l)={(x 1,x2,⋯,x1)∈ℕ0 l:x1+x2+,⋯+x1=n}. For any element u=(u1,u2⋯,ul)∈P(n,l), denote its ith-coordinate by u(i), i.e., u(i)=ui. A family ⊆P(n,l) is said to be t-intersecting if |{i:u(i)=v(i)}|≥t for all u,v∈A. We prove that given any positive integers l,t with l≥t+2, there exists a constant n0(l,t) depending only on l and t, such that for all n≥n0(l,t), if ⊆P(n,l) is t-intersecting then |A|≤(n+l-t-1 l-t-1). Moreover, the equality holds if and only if A={u∈P(n,l):u(j)=0for allj∈T} for some t-set T of {1,2,⋯,l}. © 2013 Elsevier Ltd. All rights reserved.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028142013-01-01T00:00:00Z
- An analogue of the Gallai-Edmonds Structure Theorem for non-zero roots of the matching polynomialhttps://scholarbank.nus.edu.sg/handle/10635/102815Title: An analogue of the Gallai-Edmonds Structure Theorem for non-zero roots of the matching polynomial
Authors: Ku, C.Y.; Chen, W.
Abstract: Godsil observed the simple fact that the multiplicity of 0 as a root of the matching polynomial of a graph coincides with the classical notion of deficiency. From this fact he asked to what extent classical results in matching theory generalize, replacing "deficiency" with multiplicity of θ as a root of the matching polynomial. We prove an analogue of the Stability Lemma for any given root, which describes how the matching structure of a graph changes upon deletion of a single vertex. An analogue of Gallai's Lemma follows. Together these two results imply an analogue of the Gallai-Edmonds Structure Theorem. Consequently, the matching polynomial of a vertex transitive graph has simple roots. © 2009 Elsevier Inc. All rights reserved.
Mon, 01 Mar 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028152010-03-01T00:00:00Z
- Solving the Ku-Wales conjecture on the eigenvalues of the derangement graphhttps://scholarbank.nus.edu.sg/handle/10635/104152Title: Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph
Authors: Ku, C.Y.; Wong, K.B.
Abstract: We give a new recurrence formula for the eigenvalues of the derangement graph. Consequently, we provide a simpler proof of the Alternating Sign Property of the derangement graph. Moreover, we prove that the absolute value of the eigenvalue decreases whenever the corresponding partition with a fixed first part decreases in the dominance order. In particular, this settles affirmatively a conjecture of Ku and Wales [C.Y. Ku, D.B. Wales, Eigenvalues of the derangement graph, J. Combin. Theory Ser. A 117 (2010) 289-312] regarding the lower and upper bounds for the absolute values of these eigenvalues. © 2013 Elsevier Ltd.
Thu, 01 Aug 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1041522013-08-01T00:00:00Z