All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 53

Showing per page

A characterization of planar median graphs

Iztok Peterin (2006)

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 New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected

Xiaoyun Lu, Douglas B. West (2016)

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.

A Note on Barnette’s Conjecture

Jochen Harant (2013)

Discussiones Mathematicae Graph Theory

Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.

A note on careful packing of a graph

M. Woźniak (1995)

Discussiones Mathematicae Graph Theory

Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an edge-disjoint placement of two copies of G into Kₙ. We prove that with the same condition on size of G we have actually (with few exceptions) a careful packing of G, that is an edge-disjoint placement of two copies of G into Kₙ∖Cₙ.

A note on face coloring entire weightings of plane graphs

Stanislav Jendrol, Peter Šugerek (2014)

Discussiones Mathematicae Graph Theory

Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face _ and also the weight of _. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and _ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3

Currently displaying 1 – 20 of 53

Page 1 Next