7197578
Excluding Minors In Nonplanar Graphs Of Girth At Least Five
A graph G is quasi 4-connected if it is simple, 3-connected, has at least five vertices, and for every partition (A, B, C) of V(G) either ∣C∣ ≥ 4, or G has an edge with one end in A and the other end in B, or one of A,B has at most one vertex. We show that any quasi 4-connected nonplanar graph with minimum degree at least three and no cycle of length less than five has a minor isomorphic to P−10, the Petersen graph with one edge deleted. We deduce the following weakening of Tutte's Four Flow Conjecture: every 2-edge-connected graph with no minor isomorphic to P−10 has a nowhere-zero 4-flow. This extends a result of Kilakos and Shepherd who proved the same for 3-regular graphs.
18561897
Excluding infinite minors
Let ? be an infinite cardinal, and let H be either a complete graph with ? vertices, or a tree in which every vertex has valency ?. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H?These four questions are answered for each infinite cardinal ?. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.
206570580
Sachs' Linkless Embedding Conjecture
Abstract We prove Sachs′ conjecture that a graph can be embedded in 3-space so that it contains no non-trivial link (in the sense of knot theory) if and only if it contains as a minor none of the seven graphs obtainable from K 6 by Y − Δ and Δ − Y exchanges. We also show the following: (i) A graph admits such a "linkless" embedding if and only if it admits a "panelled" embedding, one such that every circuit of the graph bounds a disc disjoint from the remainder of the graph. This was a conjecture of Bohme. (ii) An embedding is panelled if and only if for every subgraph, its complement in 3-space has free fundamental group. This extends a theorem of Scharlemann and Thompson, who proved it for planar graphs. (iii) If two panelled embeddings of the same graph are "different," that is, are not related by an orientation-preserving homeomorphism of the 3-space, then there is a subgraph which is a subdivision of K 5 or K 3, 3 such that the two induced embeddings of this subgraph are still different.
33726107
A menger-like property of tree-width: The finite case
The notion of tree-width was introduced by Robertson and Symour. A graph has tree-width ≦ w if it admits a tree-decomposition of tree-width ≦ w. We prove here that if G is finite and has tree-width ≦ w then it admits a tree-decomposition of tree-width ≦ w which satisfies a certain Menger-like condition. This result will be used in a future paper on well-quasi-ordering infinite graphs of bounded tree-width.
10511288
Clique Minors in Graphs and Their Complements
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t?1 be an integer, and let G be a graph on n vertices with no minor isomorphic to Kt+1. Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has a minor isomorphic to Ks, where s=?12(1+1/t)n?c?. We prove that Kostochka's conjecture is equivalent to the conjecture of Duchet and Meyniel that every graph with no minor isomorphic to Kt+1 has an independent set of size at least n/t. We deduce that Kostochka's conjecture holds for all integers t?5, and that a weaker form with s replaced by s?=?12(1+1/(2t))n?c? holds for all integers t?1.
2783736
List Edge-Colorings of Series-Parallel Graphs
It is proved that for every integer $k\ge3$, for every (simple) series-parallel graph $G$ with maximum degree at most $k$, and for every collection $(L(e):e\in E(G))$ of sets, each of size at least $k$, there exists a proper edge-coloring of $G$ such that for every edge $e\in E(G)$, the color of $e$ belongs to $L(e)$.
29982810
A proposal for object oriented Modula-2
31409070
Hermite interpolation with a pair of spirals
Abstract The Hermite interpolation problem in the plane considered here is to join two points and to match given unit tangent vectors and signed curvatures at the two points with various G 2 curves consisting of a pair of spirals. The rotation of the tangent vector of the interpolating curve from one point to the other is restricted to being less than π. The necessary and sufficient conditions for the existence of each of the various curves are given.
12699179
Developing the Software Engineering Team
Teamwork is often considered one of the most important "generic skills" that we can provide to graduates entering the information technology profession. Often though, through the rush of covering important content, we short change our students by giving them limited opportunities to learn how to work effectively in teams. Students also often complain that although they are expected to work in teams on projects, they are never given any advice or guidance on how to work in a team (Hart and Stone, 2002). Or, if they are given guidance, it is often from a business perspective that students find difficult to integrate into their software development practice.In this paper we discuss a course-spanning initiative to help students learn teamwork skills. This initiative starts in first year by emphasising a core set of skills directly related to working in teams. These skills are applied in small software development teams, with close tutor supervision focusing students on teamwork rather than upon individual software development. The theme then continues into second and third year where the growing sophistication of the students' teamwork skills is complemented by increasing their independence and requiring students to apply a professional software engineering process as a development team. By the end of their course students are then in a position to work together effectively solving complex problems for a real industry client.
13961083
Experimental tests of competitive markets for electric power
Testing the performance of electricity markets using POWERWEB has already shown that relatively inexperienced players can identify and exploit market power in load pockets. When transmission constraints are not binding, however, auctions with six players have been shown to be efficient. There is evidence from operating electricity markets that prices can be driven above competitive levels when the largest supplier controls less than 20% of total installed capacity. This is accomplished by causing price spikes to occur. In experiments, uncertainty about the actual load and paying standby costs regardless of whether or not a unit is actually dispatched contribute to volatile price behavior. The objective of this paper is to investigate characteristics of a market that affect price volatility. The tests consider three different sets of rules for setting price when there are capacity shortfalls, and the following four market structures: load is responsive to price; price forecasts are made before market settlement; a day-ahead market and a balancing market auction; and suppliers are paid actual offers (a discriminatory auction).
1283266
A guided clothoid spline
Abstract A method is described whereby a G 2 planar curve consisting of clothoid (Cornu spiral) segments, circular arcs and straight line segments is constructed. The curve passes through given points, is expressed parametrically, and has the attractive feature that the arc length and curvature are piecewise linear functions of the parameter. The given points through which the curve passes must be restricted somewhat so that a unique clothoid exists between each pair of points.