In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated...

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.

Let $G$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $v\in V-S$ there exists a vertex $u\in S$ such that $uv\in E\left(G\right)$. The domination number, denoted by $\gamma \left(G\right)$, is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$, then $\gamma \left(G\right)\le \frac{4}{11}n$.

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 ${\gamma }_{\times 2}\left(G\right)$. A function f(p) is defined, and it is shown that ${\gamma }_{\times 2}\left(G\right)=minf\left(p\right)$, where the minimum is taken over the n-dimensional cube $Cⁿ=p=(p₁,...,pₙ)|p_i\in IR,0\le p_i\le 1,i=1,...,n$. Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then ${\gamma }_{\times 2}\left(G\right)\le ((ln(1+d)+ln\delta +1)/\delta )n$.

A vertex is said to be doubly light in a family of plane graphs if its degree and sizes of neighbouring faces are bounded above by a finite constant. We provide several results on the existence of doubly light vertices in various families of plane graph.

We discuss dual Ramsey statements for several classes of finite relational structures (such as finite linearly ordered graphs, finite linearly ordered metric spaces and finite posets with a linear extension) and conclude the paper with another rendering of the Nešetřil-Rödl Theorem for relational structures. Instead of embeddings which are crucial for ``direct'' Ramsey results, for each class of structures under consideration we propose a special class of quotient maps and prove a dual Ramsey theorem...

A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible graph. A (finite...

For two vertices u and v in a graph G = (V,E), the detour distance D(u,v) is the length of a longest u-v path in G. A u-v path of length D(u,v) is called a u-v detour. A set S ⊆V is called an edge detour set if every edge in G lies on a detour joining a pair of vertices of S. The edge detour number dn₁(G) of G is the minimum order of its edge detour sets and any edge detour set of order dn₁(G) is an edge detour basis of G. A connected graph G is called an edge detour graph if it has an edge detour...

Let $G$ be a mixed graph. The eigenvalues and eigenvectors of $G$ are respectively defined to be those of its Laplacian matrix. If $G$ is a simple graph, [M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (1975), 619–633] gave a remarkable result on the structure of the eigenvectors of $G$ corresponding to its second smallest eigenvalue (also called the algebraic connectivity of $G$). For $G$ being a general mixed graph with...