A bisection method for the traveling salesman problem
A bound on the -domination number of a graph
Let be a graph with vertex set , and let be an integer. A subset is called a -dominating set if every vertex has at least neighbors in . The -domination number of is the minimum cardinality of a -dominating set in . If is a graph with minimum degree , then we prove that In addition, we present a characterization of a special class of graphs attaining equality in this inequality.
A characterization of diameter-2-critical graphs with no antihole of length four
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence...
A characterization of graphs in which some minimum dominating set covers all the edges
A characterization of the decay number of a connected graph
A combinatorial ranking problem.
A combinatorial ranking problem. (Short Communication).
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 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 Décomposition Theorem on Euclidean Steiner Minimal Trees.
A Different Short Proof of Brooks’ Theorem
Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.
A generalization of a theorem of Turán for valuated graphs
A generalization of Hamiltonian cycles for trees
A graph and its complement with specified properties. III: Girth and circumference.
A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs.
A linear pseudo-Boolean viewpoint on matching and other central concepts in graph theory
A local limit theorem for the critical random graph.
A lower bound for Schur numbers and multicolor Ramsey numbers.
A lower bound for the number of edges in a graph containing no two cycles of the same length.
A maximum degree theorem for diameter-2-critical graphs
A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a...