Let n, s and t be three integers with s ≥ 1, t ≥ 0 and n = 3s + 4t. Let G be a graph of order n such that the minimum degree of G is at least (n + s)/2. Then G contains a 2-factor with s + t components such that s of them are triangles and t of them are quadrilaterals.

Les dissimilarités multivoies sont une généralisation naturelle des dissimilarités usuelles deux voies. Dans ce papier, des classes de dissimilarités multivoies sont étudiées, ainsi que des modèles de passage d'un nombre de voies donné à un autre nombre de voies. Une application à la spécification de systèmes classifiants a conduit à une bijection entre une classe de dissimilarités multivoies et une famille de systèmes stratifiés de classifccation.

A set of vertices D of a graph G is a distance 2-dominating set of G if the distance between each vertex u ∊ (V (G) − D) and D is at most two. Let γ2(G) denote the size of a smallest distance 2-dominating set of G. For any permutation π of the vertex set of G, the prism of G with respect to π is the graph πG obtained from G and a copy G′ of G by joining u ∊ V(G) with v′ ∊ V(G′) if and only if v′ = π(u). If γ2(πG) = γ2(G) for any permutation π of V(G), then G is called a universal γ2-fixer. In this...

Motivated by the frequency assignment problem we study the d-distant coloring of the vertices of an infinite plane hexagonal lattice H. Let d be a positive integer. A d-distant coloring of the lattice H is a coloring of the vertices of H such that each pair of vertices distance at most d apart have different colors. The d-distant chromatic number of H, denoted ${\chi }_d\left(H\right)$, is the minimum number of colors needed for a d-distant coloring of H. We give the exact value of ${\chi }_d\left(H\right)$ for any d odd and estimations for any...

For a spanning tree T in a nontrivial connected graph G and for vertices u and v in G, there exists a unique u-v path u = u₀, u₁, u₂,..., uₖ = v in T. A u-v T-path in G is a u- v path u = v₀, v₁,...,vₗ = v in G that is a subsequence of the sequence u = u₀, u₁, u₂,..., uₖ = v. A u-v T-path of minimum length is a u-v T-geodesic in G. The T-distance $d_{G|T}(u,v)$ from u to v in G is the length of a u-v T-geodesic. Let geo(G) and geo(G|T) be the set of geodesics and the set of T-geodesics respectively in G. Necessary...

A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$, the $X$-eccentricity $e_X\left(v\right)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$-colored vertex furthest from $v$. The minimum $X$-eccentricity among the vertices of $G$ is the $X$-radius ${\mathrm{r}ad}_{X}G$ of $G$ and the maximum...

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number ${\beta }_D\left(G\right)$ is the maximum cardinality of a D-independent set. In particular, the independence number $\beta \left(G\right)={\beta }_1\left(G\right)$. Along with general results we consider, in particular, the odd-independence number ${\beta }_{ODD}\left(G\right)$ where ODD = 1,3,5,....

A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ : V → {1, . . . , n} such that the weight of every vertex v, computed as the sum of the labels on the vertices in the open neighborhood of v, is a constant. In this paper, we show that hypercubes with dimension divisible by four are not distance magic. We also provide some positive results by proving necessary and sufficient conditions for the Cartesian product of certain complete multipartite graphs and the cycle on four...

Let $T$ be a tree with $n$ vertices. To each edge of $T$ we assign a weight which is a positive definite matrix of some fixed order, say, $s$. Let $D_{ij}$ denote the sum of all the weights lying in the path connecting the vertices $i$ and $j$ of $T$. We now say that $D_{ij}$ is the distance between $i$ and $j$. Define $D:=\left[D_{ij}\right]$, where $D_{ii}$ is the $s\times s$ null matrix and for $i\ne j$, $D_{ij}$ is the distance between $i$ and $j$. Let $G$ be an arbitrary connected weighted graph with $n$ vertices, where each weight is a positive definite matrix of order $s$. If $i$ and...