We show that every plane graph with maximum face size four in which all faces of size four are vertex-disjoint is cyclically 5-colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5-colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory
domingo, 22 de noviembre de 2009
Coloring plane graphs with independent crossings
We show that every plane graph with maximum face size four in which all faces of size four are vertex-disjoint is cyclically 5-colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5-colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory
Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
A balloon in a graph G is a maximal 2-edge-connected subgraph incident to exactly one cut-edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut-edges, and let [alpha][prime](G) be the maximum size of a matching. Let be the family of connected (2r+1)-regular graphs with n vertices, and let . For , we prove the sharp inequalities c(G)[les][r(n-2)-2]/(2r2+2r-1)-1 and [alpha][prime](G)[ges]n/2-rb/(2r+1). Using b[les][(2r-1)n+2]/(4r2+4r-2), we obtain a simple proof of the bound proved by Henning and Yeo. For each of these bounds and each r, the approach using balloons allows us to determine the infinite family where equality holds. For the total domination number [gamma]t(G) of a cubic graph, we prove [gamma]t(G)[les]n/2-b(G)/2 (except that [gamma]t(G) may be n/2-1 when b(G)=3 and the balloons cover all but one vertex). With [alpha][prime](G)[ges]n/2-b(G)/3 for cubic graphs, this improves the known inequality [gamma]t(G)[les][alpha][prime](G). © 2009 Wiley Periodicals, Inc. J Graph Theory
Choosability of toroidal graphs without short cycles
Let G be a toroidal graph without cycles of a fixed length k, and [chi]l(G) the list chromatic number of G. We establish tight upper bounds of [chi]l(G) for the following values of k: © 2009 Wiley Periodicals, Inc. J Graph Theory
The geometry of t-spreads in k-walk-regular graphs
A graph is walk-regular if the number of closed walks of length [ell] rooted at a given vertex is a constant through all the vertices for all [ell]. For a walk-regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d-spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three-dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k-walk-regular graphs, a family which includes both walk-regular and distance-regular graphs, and their t-spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory
On Ramsey-type positional games
Beck introduced the concept of Ramsey games by studying the game versions of Ramsey and van der Waerden theorems. We contribute to this topic by investigating games corresponding to structural extensions of Ramsey and van der Waerden theorems - the theorem of Brauer, structural and restricted Ramsey theorems. © 2009 Wiley Periodicals, Inc. J Graph Theory
On recognizing graphs by numbers of homomorphisms
Let hom (G, H) be the number of homomorphisms from a graph G to a graph H. A well-known result of Lovász states that the function hom (·, H) from all graphs uniquely determines the graph H up to isomorphism. We study this function restricted to smaller classes of graphs. We show that several natural classes (2-degenerate graphs and graphs homomorphic to an arbitrary non-bipartite graph) are sufficient to recognize all graphs, and provide a description of graph properties that are recognizable by graphs with bounded tree-width. © 2009 Wiley Periodicals, Inc. J Graph Theory
Brown, IBM Unveil Multimillion-Dollar Supercomputer
Brown University and IBM today announced the opening of a multimillion-dollar supercomputer at Brown's Center for Computation and Visualization.
Preservation and destruction of periodic orbits by symplectic integrators
Abstract We investigate what happens to periodic orbits and lower-dimensional tori of Hamiltonian systems under discretisation by a
symplectic one-step method where the system may have more than one degree of freedom. We use an embedding of a symplectic
map in a quasi-periodic non-autonomous flow and a KAM result of Jorba and Villaneuva (J Nonlinear Sci 7:427–473, 1997) to show that periodic orbits persist in the new flow, but with slightly perturbed period and an additional degree of freedom
when the map is non-resonant with the periodic orbit. The same result holds for lower-dimensional tori with more degrees of
freedom. Numerical experiments with the two degree of freedom Hénon–Heiles system are used to show that in the case where
the method is resonant with the periodic orbit, the orbit is destroyed and replaced by two invariant sets of periodic points—analogous
to what is understood for one degree of freedom systems.
symplectic one-step method where the system may have more than one degree of freedom. We use an embedding of a symplectic
map in a quasi-periodic non-autonomous flow and a KAM result of Jorba and Villaneuva (J Nonlinear Sci 7:427–473, 1997) to show that periodic orbits persist in the new flow, but with slightly perturbed period and an additional degree of freedom
when the map is non-resonant with the periodic orbit. The same result holds for lower-dimensional tori with more degrees of
freedom. Numerical experiments with the two degree of freedom Hénon–Heiles system are used to show that in the case where
the method is resonant with the periodic orbit, the orbit is destroyed and replaced by two invariant sets of periodic points—analogous
to what is understood for one degree of freedom systems.
- Content Type Journal Article
- Category Original Paper
- DOI 10.1007/s11075-009-9352-6
- Authors
- Robert I. McLachlan, Massey University I.F.S. Palmerston North New Zealand
- Dion R. J. O’Neale, Massey University I.F.S. Palmerston North New Zealand
- Journal Numerical Algorithms
- Online ISSN 1572-9265
- Print ISSN 1017-1398
Suscribirse a:
Entradas (Atom)