The number of 1-factors in some polyhexes.
The order of uniquely partitionable graphs
Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by has property . If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.
The packing and covering of the complete graph. I: The forests of order five.
The Regulation Number of a Graph
The Ryjáček Closure and a Forbidden Subgraph
The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.
The signed matchings in graphs
Let G be a graph with vertex set V(G) and edge set E(G). A signed matching is a function x: E(G) → -1,1 satisfying for every v ∈ V(G), where . The maximum of the values of , taken over all signed matchings x, is called the signed matching number and is denoted by β’₁(G). In this paper, we study the complexity of the maximum signed matching problem. We show that a maximum signed matching can be found in strongly polynomial-time. We present sharp upper and lower bounds on β’₁(G) for general graphs....
The space of complete subgraphs of a graph
The s-packing chromatic number of a graph
Let S = (a₁, a₂, ...) be an infinite nondecreasing sequence of positive integers. An S-packing k-coloring of a graph G is a mapping from V(G) to 1,2,...,k such that vertices with color i have pairwise distance greater than , and the S-packing chromatic number of G is the smallest integer k such that G has an S-packing k-coloring. This concept generalizes the concept of proper coloring (when S = (1,1,1,...)) and broadcast coloring (when S = (1,2,3,4,...)). In this paper, we consider bounds on...
The stable roommates problem and chess tournament pairings.
The structure and existence of 2-factors in iterated line graphs
We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where contains a 2-factor.
The tree-covering number of a graph
The -polynomials of complete graphs are real.
Tiling parity results and the holey square solution.
Total domination in categorical products of graphs
Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination number on the...
Total edge-domatic number of a graph
The total edge-domatic number of a graph is introduced as an edge analogue of the total domatic number. Its values are studied for some special classes of graphs. The concept of totally edge-domatically full graph is introduced and investigated.
Towards the distribution of the size of a largest planar matching and largest planar subgraph in random bipartite graphs.
Trees and matchings.
Trees with α-labelings and decompositions of complete graphs into non-symmetric isomorphic spanning trees
We examine constructions of non-symmetric trees with a flexible q-labeling or an α-like labeling, which allow factorization of into spanning trees, arising from the trees with α-labelings.
Triangle Decompositions of Planar Graphs
A multigraph G is triangle decomposable if its edge set can be partitioned into subsets, each of which induces a triangle of G, and rationally triangle decomposable if its triangles can be assigned rational weights such that for each edge e of G, the sum of the weights of the triangles that contain e equals 1. We present a necessary and sufficient condition for a planar multigraph to be triangle decomposable. We also show that if a simple planar graph is rationally triangle decomposable, then it...