Page 1 Next

## Displaying 1 – 20 of 464

Showing per page

### 1-bend 3-D orthogonal box-drawings: Two open problems solved.

Journal of Graph Algorithms and Applications

### 1-factors and characterization of reducible faces of plane elementary bipartite graphs

Discussiones Mathematicae Graph Theory

As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of...

### 3-Paths in Graphs with Bounded Average Degree

Discussiones Mathematicae Graph Theory

In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types [...] Moreover, no parameter of this description can be improved.

### 3-polytopes of constant tolerance of edges

Commentationes Mathematicae Universitatis Carolinae

### 4-critical 4-valent planar graphs constructed with crowns.

Mathematica Scandinavica

### 5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5

Discussiones Mathematicae Graph Theory

It is known that there are normal plane maps M5 with minimum degree 5 such that the minimum degree-sum w(S5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M5 with w(S5) = 48

### A characterization of planar median graphs

Discussiones Mathematicae Graph Theory

Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.

### A combinatorial characterization of 4-dimensional handlebodies.

Forum mathematicum

### A complete grammar for decomposing a family of graphs into 3-connected components.

The Electronic Journal of Combinatorics [electronic only]

### A fast multi-scale method for drawing large graphs.

Journal of Graph Algorithms and Applications

### A formula for the bivariate map asymptotics constants in terms of the univariate map asymptotics constants.

The Electronic Journal of Combinatorics [electronic only]

### A Hamiltonian property of connected sets in the alternative set theory.

Acta Mathematica Universitatis Comenianae. New Series

### A Kotzig type theorem for non-orientable surfaces

Mathematica Slovaca

### A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs.

Journal of Graph Algorithms and Applications

### A linear algorithm to recognize maximal generalized outerplanar graphs

Mathematica Bohemica

In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.

### A Lower Bound for the Optimal Crossing-Free Hamiltonian Cycle Problem.

Discrete &amp; computational geometry

### A Maximal Toroidal Graph which is not a Triangulation.

Mathematica Scandinavica

### A new characterization of the maximum genus of a graph

Czechoslovak Mathematical Journal

### A new proof of the four-colour theorem.

Electronic Research Announcements of the American Mathematical Society [electronic only]

### A New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected

Discussiones Mathematicae Graph Theory

We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.

Page 1 Next