Search

Your search keyword '"Colbourn, Charles J."' showing total 49 results
Start Over Author "Colbourn, Charles J." Journal discrete mathematics
49 results on '"Colbourn, Charles J."'

28. -vectors of pure complexes and pure multicomplexes of rank three.

Author

Colbourn, Charles J., Keranen, M.S., and Kreher, D.L.

Subjects
*VECTOR analysis, *MATHEMATICAL complexes, *NUMBER theory, *MATHEMATICAL proofs, *COMBINATORIAL set theory, *INTEGERS
Abstract

Abstract: Necessary and sufficient conditions are established for an integer vector to be the -vector of some pure simplicial complex of rank three, and also for an integer vector to be the -vector of some pure simplicial multicomplex of rank three. For specified numbers of sets of cardinality one and cardinality two, an upper bound on the number of sets of cardinality three is established using shifting arguments. Then techniques from combinatorial design theory are used to establish a lower bound. Then it is shown that every number of sets of cardinality three between the lower and the upper bound can be realized. This characterization is restated to determine the precise spectrum of possible numbers of sets of cardinality two for specified numbers of sets of cardinality one and three. For simplicial complexes, these spectra are not always intervals, and the gaps are determined precisely. For simplicial multicomplexes, an alternative proof is given that these spectra are always intervals. [Copyright &y& Elsevier]

Published
2014
Full Text
View/download PDF

37. Unit disk graphs

Author

Clark, Brent N., primary, Colbourn, Charles J., additional, and Johnson, David S., additional

Published
1990
Full Text
View/download PDF

41. Grooming in unidirectional rings: <f>K4-e</f> designs

Author

Bermond, Jean-Claude, Colbourn, Charles J., Ling, Alan C.H., and Yu, Min-Li

Subjects
*GRAPHIC methods, *GRAPH theory, *ALGEBRA, *MATHEMATICS
Abstract

In wavelength division multiplexing for unidirectional rings, traffic grooming is used to pack low rate signals into higher rate streams to share a wavelength. The grooming chosen determines the number of add-drop multiplexers used for the optical-to-electronic conversion. The determination of groomings to use the fewest multiplexers is equivalent to a graph design problem, which has been solved when up to four signals can be packed into a stream. We completely settle the case here when five signals pack into one stream, using old and new results on (K4-e)-designs. [Copyright &y& Elsevier]

Published
2004
Full Text
View/download PDF

42. Minimum embedding of Steiner triple systems into (K4−e)-designs II

Author

Ling, Alan C.H., Colbourn, Charles J., and Quattrocchi, Gaetano

Subjects
Embedding
Abstract

A (K4−e)-design of order v+w embeds a given Steiner triple system if there is a subset of v points on which the graphs of the design induce the blocks of the original Steiner triple system. It has been established that w≥v/3, and that when equality is met, such a minimum embedding of an STS(v) exists, except when v=15. Equality only holds when v≡15,27(mod30). One natural question is: What is the smallest order w such that some STS(v) can be embedded into a (K4−e)-design of order v+w? We solve the problem for 7 of the 10 congruence classes modulo 30.

Full Text
View/download PDF

43. Minimum embedding of Steiner triple systems into (K4-e)-designs I

Author

Colbourn, Charles J., Ling, Alan C.H., and Quattrocchi, Gaetano

Subjects
Design embedding, Steiner triple system, Resolvable design, Graph design
Abstract

A (K4-e)-design on v+w points embeds a Steiner triple system (STS) if there is a subset of v points on which the graphs of the design induce the blocks of a STS. It is established that w⩾v/3, and that when equality is met that such a minimum embedding of an STS(v) exists, except when v=15.

Full Text
View/download PDF

44. Edge-packing of graphs and network reliability

Author

Colbourn, Charles J.

Abstract

The reliability of a network can be efficiently bounded using graph-theoretical techniques based on edge-packing. We examine the application of combinatorial theorems on edge-packing spanning trees, s, t-paths, and s, t-cuts to the determination of reliability bounds. The application of spanning trees has been studied by Polesskii, and the application of s, t-paths has been studied by Brecht and Colbourn. The use of edge-packings of s, t-cutsets has not been previously examined. We compare the resulting bounds with known bounds produced by different techniques, and establish that the edge-packing bounds often produce a substantial improvement. We also establish that three other edge-packing problems arising in reliability bounding are NP-complete, namely edge-packing by network cutsets, Steiner trees, and Steiner cutsets.

Published
1988
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results