On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

Elementary submodels in infinite combinatorics

The use of elementary submodels is a simple but powerful method to prove theorems, or to simplify proofs in infinite combinatorics. First we introduce all the necessary concepts of logic, then we prove classical theorems using elementary submodels. We also present a new proof of Nash-Williams’s theorem on cycle decomposition of graphs, and finally we improve a decomposition theorem of Laviolette concerning bond-faithful decompositions of graphs.     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

A polynomial algorithm for the max-cut problem on graphs without long odd cycles

Given a graphG=[V, E] with positive edge weights, the max-cut problem is to find a cut inG such that the sum of the weights of the edges of this cut is as large as possible. Letg(K) be the class of graphs whose longest odd cycle is not longer than2K+1, whereK is a nonnegative integer independent of the numbern of nodes ofG. We present an O(n ^4K) algorithm for the max-cut problem for graphs ing(K). The algorithm is recursive and is based on some properties of longest and longest odd cycles of graphs. This research was supported by National Science Foundation Grant ECS-8005350 to Cornell University.     

The biobjective absolute center problem

This paper deals with the problem of determining the absolute center of a network, taking into account two objective functions. These functions consist of minimizing the maximum of the distances from any point on the network to the vertices, using two independent lengths on each edge. We propose an algorithm in polynomial time to obtain the non-dominated location points on the network, using the Kariv and Hakimi method (1979). This work was partially supported by project number 93/108 from the Dirección General de Universidades e Investigación del Gobierno de Canarias.     

Fitting Height and Diameter of Character Degree Graphs

Let a graph Γ have bounded Fitting height (i.e., there is a bound on the Fitting heights of those groups whose character degree graph is Γ) and G be any solvable group with character degree graph Γ and Fitting height h(G). We improve Moretò's bound by proving that if no vertex in Γ is adjacent to every other one, then h(G) ≤4, else h(G) ≤6. As a consequence, if a solvable group G has character degree graph with diameter 3, then h(G) ≤4. Moreover, G has at most one non-abelian normal Sylow subgroup in this case.     

Full Graphs and Koszul Algebras I

The main result of this article is the establishment of a new connection between combinatorics and noncommutative algebra. This is done by linking a certain class of directed graphs, called full graphs, to quotients of path algebras that are Koszul algebras.