François Jaeger conjectured in 1974 that every cyclically 4-connected cubic graph $G$ is dual hamiltonian, that is to say the vertices of $G$ can be partitioned into two subsets such that each subset induces a tree in $G$. We shall make several remarks on this conjecture.

A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least k. We show...

Let α ∈ (0,1) and let $G=(V_G,E_G$) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D\subseteq V_G$ is called an α-dominating set of G, if $|N_G\left(u\right)\cap D|\ge \alpha d_G\left(u\right)$ for all $u\in V_G\setminus D$. We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.

Let S be a cut of a simple connected graph G. If S has no proper subset that is a cut, we say S is a minimal cut of G. To a minimal cut S, a connected component of G-S is called a fragment. And a fragment with no proper subset that is a fragment is called an end. In the paper ends are characterized and it is proved that to a connected graph G = (V,E), the number of its ends Σ ≤ |V(G)|.

Let D be a digraph with set of vertices V and set of arcs A. We say that D is k-transitive if for every pair of vertices u, v ∈ V, the existence of a uv-path of length k in D implies that (u, v) ∈ A. A 2-transitive digraph is a transitive digraph in the usual sense. A subset N of V is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent...

Using isometric embedding of metric trees into Banach spaces, this paper will investigate barycenters, type and cotype, and various measures of compactness of metric trees. A metric tree (T, d) is a metric space such that between any two of its points there is a unique arc that is isometric to an interval in ℝ. We begin our investigation by examining isometric embeddings of metric trees into Banach spaces. We then investigate the possible images x₀ = π((x₁ + ... + xₙ)/n), where π is a contractive...

A signed graph (or sigraph in short) is an ordered pair $S=(S^u,\sigma )$, where $S^u$ is a graph G = (V,E), called the underlying graph of S and σ:E → +, - is a function from the edge set E of $S^u$ into the set +,-, called the signature of S. The ×-line sigraph of S denoted by $L_{\times }\left(S\right)$ is a sigraph defined on the line graph $L\left(S^u\right)$ of the graph $S^u$ by assigning to each edge ef of $L\left(S^u\right)$, the product of signs of the adjacent edges e and f in S. In this paper, first we define semi-total line sigraph and semi-total point sigraph of a given...

Let $R$ be a commutative ring. The annihilator graph of $R$, denoted by $\mathrm{AG}\left(R\right)$, is the undirected graph with all nonzero zero-divisors of $R$ as vertex set, and two distinct vertices $x$ and $y$ are adjacent if and only if ${\mathrm{ann}}_R\left(xy\right)\ne {\mathrm{ann}}_R\left(x\right)\cup {\mathrm{ann}}_R\left(y\right)$, where for $z\in R$, ${\mathrm{ann}}_R\left(z\right)=\{r\in R:rz=0\}$. In this paper, we characterize all finite commutative rings $R$ with planar or outerplanar or ring-graph annihilator graphs. We characterize all finite commutative rings $R$ whose annihilator graphs have clique number $1$, $2$ or $3$. Also, we investigate some properties of the annihilator...