An edge $e$ of a $k$-connected graph $G$ is said to be $k$-contractible (or simply contractible) if the graph obtained from $G$ by contracting $e$ (i.e., deleting $e$ and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still $k$-connected. In 2002, Kawarabayashi proved that for any odd integer $k\ge 5$, if $G$ is a $k$-connected graph and $G$ contains no subgraph $D=K_1+(K_2\cup K_{1,2})$, then $G$ has a $k$-contractible edge. In this paper, by generalizing this result, we prove that for any integer...

The control flow of programs can be represented by directed graphs. In this paper we provide a uniform and detailed formal basis for control flow graphs combining known definitions and results with new aspects. Two graph reductions are defined using only syntactical information about the graphs, but no semantical information about the represented programs. We prove some properties of reduced graphs and also about the paths in reduced graphs. Based on graphs, we define statement coverage and branch...

In this paper we characterize the convex dominating sets in the composition and Cartesian product of two connected graphs. The concepts of clique dominating set and clique domination number of a graph are defined. It is shown that the convex domination number of a composition $G\left[H\right]$ of two non-complete connected graphs $G$ and $H$ is equal to the clique domination number of $G$. The convex domination number of the Cartesian product of two connected graphs is related to the convex domination numbers of the...

We investigate the convex invariants associated with two-path convexity in clone-free multipartite tournaments. Specifically, we explore the relationship between the Helly number, Radon number and rank of such digraphs. The main result is a structural theorem that describes the arc relationships among certain vertices associated with vertices of a given convexly independent set. We use this to prove that the Helly number, Radon number, and rank coincide in any clone-free bipartite tournament. We...

In [1] Burger and Mynhardt introduced the idea of universal fixers. Let G = (V, E) be a graph with n vertices and G’ a copy of G. For a bijective function π: V(G) → V(G’), define the prism πG of G as follows: V(πG) = V(G) ∪ V(G’) and $E\left(\pi G\right)=E\left(G\right)\cup E\left(G^{\text{'}}\right)\cup M_{\pi }$, where $M_{\pi }=u\pi \left(u\right)\left|u\in V\right(G)$. Let γ(G) be the domination number of G. If γ(πG) = γ(G) for any bijective function π, then G is called a universal fixer. In [9] it is conjectured that the only universal fixers are the edgeless graphs K̅ₙ. In this work we generalize the concept of universal...

The $k$-core of a graph $G$, $C_k\left(G\right)$, is the maximal induced subgraph $H\subseteq G$ such that $\delta \left(G\right)\ge k$, if it exists. For $k>0$, the $k$-shell of a graph $G$ is the subgraph of $G$ induced by the edges contained in the $k$-core and not contained in the $(k+1)$-core. The core number of a vertex is the largest value for $k$ such that $v\in C_k\left(G\right)$, and the maximum core number of a graph, $\widehat{C}\left(G\right)$, is the maximum of the core numbers of the vertices of $G$. A graph $G$ is $k$-monocore if $\widehat{C}\left(G\right)=\delta \left(G\right)=k$. This paper discusses some basic results on the structure of $k$-cores and $k$-shells....