A combinatorial approach to the conditioning of a single entry in the stationary distribution for a Markov chain.
A combinatorial characterization of 4-dimensional handlebodies.
A combinatorial derivation of the number of labeled forests.
A combinatorial interpretation of homotopy groups of polyhedra
A combinatorial proof of Postnikov's identity and a generalized enumeration of labeled trees.
A combinatorial property and power graphs of semigroups
Research on combinatorial properties of sequences in groups and semigroups originates from Bernhard Neumann's theorem answering a question of Paul Erd"{o}s. For results on related combinatorial properties of sequences in semigroups we refer to the book [3]. In 2000 the authors introduced a new combinatorial property and described all groups satisfying it. The present paper extends this result to all semigroups.
A combinatorial ranking problem.
A combinatorial ranking problem. (Short Communication).
A complete grammar for decomposing a family of graphs into 3-connected components.
A conjecture of Biggs concerning the resistance of a distance-regular graph.
A conjecture on cycle-pancyclism in tournaments
Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote , the number of arcs that γ and Cₖ have in common. Let and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave...
A conjecture on the prevalence of cubic bridge graphs
Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.
A construction of geodetic blocks
A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles
For any we construct graphs of degree , diameter , and order , obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of has been known [3] but it applies only to special values of degrees depending on prime powers.
A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs
Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = {x1, . . . , xm} and Y = {y1, . . . , yn} such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for...
A deceptive fact about functions
The paper provides a proof of a combinatorial result which pertains to the characterization of the set of equations which are solvable in the composition monoid of all partial functions on an infinite set.
A decomposition algorithm for the oriented adjacency graph of the triangulations of a bordered surface with marked points.
A decomposition of gallai multigraphs
An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees...
A Décomposition Theorem on Euclidean Steiner Minimal Trees.
A degree condition for the existence of -factors with prescribed properties.