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.
For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.
For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.
For a connected and non-complete graph, a new lower bound on its independence number is proved. It is shown that this bound is realizable by the well known efficient algorithm MIN.
Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.
DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.
Necessary conditions for an undirected graph G to contain a graph H as induced subgraph involving the smallest ordinary or the largest normalized Laplacian eigenvalue of G are presented.
For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number . A function f(p) is defined, and it is shown that , where the minimum is taken over the n-dimensional cube . Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then .
The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds 2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds 3. Let G be a 3-connected simple planar graph of circumference...
A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover,...
Let be a set of graphs and for a graph G let and denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on and are presented.
Page 1