Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Combinatorics (10)
- Fibonacci numbers (6)
- Graphs (5)
- Combinatorial identities (3)
- Bijections (2)
-
- Bipartite graphs (2)
- Bollobás (2)
- Cellular automata (2)
- Discrete mathematics (2)
- Finite automata (2)
- Firing squad synchronization problem (2)
- Involution (2)
- Macdonald polynomials (2)
- Published Research Papers (2)
- Subgraphs (2)
- 05A05 (1)
- 05A19 (1)
- 05E05 (1)
- Alternating sum (1)
- Analysis of algorithms (1)
- Binomial coefficients (1)
- Binomial identity (1)
- Braided tensor category (1)
- Characteristic equation (1)
- Combinatorial proofs (1)
- Commutative Algebra (1)
- Computational thinking (1)
- Computer science education (1)
- Conjecture (1)
- Continued Fractions (1)
- Publication Year
Articles 31 - 42 of 42
Full-Text Articles in Discrete Mathematics and Combinatorics
Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West
Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West
Noah Prince
A Roman dominating function of a graph G is a labeling f: V(G) →{0,1,2} such that every vertex with a label 0 has a neighbor with label 2. The Roman domination number γR(G) of G is the minimum of ∑ʋϵV(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γR(G) ≤ 4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γR(G) + …
Highly Connected Multicoloured Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince
Highly Connected Multicoloured Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince
Hua Kun Liu
Suppose the edges of the complete graph on n vertices, E(Kn), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s is greater than or equal to 2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4 and that …
The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz
The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz
Noah Prince
Erdös and Lovász conjectured in 1968 that for every graph G with χ(G) > ω(G) and any two integers s, t ≥ 2 with s + t = χ(G) + 1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S]) ≥ s and χ(G[T]) ≥ t . Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.
Highly Connected Multicoloured Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince
Highly Connected Multicoloured Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince
Noah Prince
Suppose the edges of the complete graph on n vertices, E(Kn), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s is greater than or equal to 2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4 and that …
On KS,T-Minors In Graphs With Given Average Degree, A. V. Kostochka, N. Prince
On KS,T-Minors In Graphs With Given Average Degree, A. V. Kostochka, N. Prince
Noah Prince
Let D(H) be the minimum d such that every graph G with average degree d has an H-minor. Myers and Thomason found good bounds on D(H) for almost all graphs H and proved that for 'balanced' H random graphs provide extremal examples and determine the extremal function. Examples of 'unbalanced graphs' are complete bipartite graphs Ks,t for a fixed s and large t. Myers proved upper bounds on D(Ks,t ) and made a conjecture on the order of magnitude of D(Ks,t ) for a fixed s and …
On The Gauge Equivalence Of Twisted Quantum Doubles Of Elementary Abelian And Extra-Special 2-Groups, Christopher Goff, Geoffrey Mason, Siu-Hung Ng
On The Gauge Equivalence Of Twisted Quantum Doubles Of Elementary Abelian And Extra-Special 2-Groups, Christopher Goff, Geoffrey Mason, Siu-Hung Ng
Christopher Goff
An Explicit Fusion Algebra Isomorphism For Twisted Quantum Doubles Of Finite Groups, Christopher Goff
An Explicit Fusion Algebra Isomorphism For Twisted Quantum Doubles Of Finite Groups, Christopher Goff
Christopher Goff
Bounding The Firing Synchronization Problem On A Ring, André Berthiaume, Todd Bittner, Ljubomir Perković, Amber Settle, Janos Simon
Bounding The Firing Synchronization Problem On A Ring, André Berthiaume, Todd Bittner, Ljubomir Perković, Amber Settle, Janos Simon
Amber Settle
A Family Of Isomorphic Fusion Algebras Of Twisted Quantum Doubles Of Finite Groups, Christopher Goff
A Family Of Isomorphic Fusion Algebras Of Twisted Quantum Doubles Of Finite Groups, Christopher Goff
Christopher Goff
Smaller Solutions For The Firing Squad, Amber Settle, Janos Simon
Smaller Solutions For The Firing Squad, Amber Settle, Janos Simon
Amber Settle
Explicit Inversion Formulas For Toeplitz Band Matrices, William F. Trench
Explicit Inversion Formulas For Toeplitz Band Matrices, William F. Trench
William F. Trench
No abstract provided.
On Periodicities Of Certain Sequences Of Residues, William F. Trench
On Periodicities Of Certain Sequences Of Residues, William F. Trench
William F. Trench
No abstract provided.