Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)

Jan Florek

The search session has expired. Please query the service again.

Displaying similar documents to “Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)”

Pairs of forbidden class of subgraphs concerning $K_{1, 3}$ and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama, Masao Tsugaki (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1, 3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1, 3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

Graceful signed graphs

Mukti Acharya, Tarkeshwar Singh (2004)

Czechoslovak Mathematical Journal

Similarity:

A $(p, q)$ -sigraph $S$ is an ordered pair $(G, s)$ where $G = (V, E)$ is a $(p, q)$ -graph and $s$ is a function which assigns to each edge of $G$ a positive or a negative sign. Let the sets $E^{+}$ and $E^{-}$ consist of $m$ positive and $n$ negative edges of $G$ , respectively, where $m + n = q$ . Given positive integers $k$ and $d$ , $S$ is said to be $(k, d)$ -graceful if the vertices of $G$ can be labeled with distinct integers from the set ${0, 1, \dots, k + (q - 1) d}$ such that when each edge $u v$ of $G$ is assigned the product of its sign and the absolute difference of the integers assigned to...

On light subgraphs in plane graphs of minimum degree five

Stanislav Jendrol&#039;, Tomáš Madaras (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1, 3}$ and $K_{1, 4}$ and a light 4-path P₄. The results obtained for $K_{1, 3}$ and P₄ are best possible.

On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a ${d, d + k}$ -graph, if one vertex has degree $d + k$ and the remaining vertices of $G$ have degree $d$ . In the special case of $k = 0$ , the graph $G$ is $d$ -regular. Let $k, p \geq 0$ and $d, n \geq 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected ${d, d + k}$ -graph of order $n$ without a matching $M$ of size $2 | M | = n - p$ , then we show in this paper the following: If $d = 2$ , then $k \geq 2 (p + 2)$ and (i) $n \geq k + p + 6$ . If $d \geq 3$ is odd and $t$ an integer with $1 \leq t \leq p + 2$ , then (ii) $n \geq d + k + 1$ for $k \geq d (p + 2)$ , (iii) $n \geq d (p + 3) + 2 t + 1$ for $d (p + 2 - t) + t \leq k \leq d (p + 3 - t) + t - 3$ , (iv) $n \geq d (p + 3) + 2 p + 7$ for $k \leq p$ . If $d \geq 4$ is even, then (v) $n \geq d + k + 2 - η$ for $k \geq d (p + 3) + p + 4 + η$ , (vi) $n \geq d + k + p + 2 - 2 t = d (p + 4) + p + 6$ for $k = d (p + 3) + 4 + 2 t$ and $p \geq 1$ ,...

Decomposition of Cartesian product of complete graphs into paths and stars with four edges

Arockiajeyaraj P. Ezhilarasi, Appu Muthusamy (2021)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let $P_{k}$ and $S_{k}$ denote a path and a star, respectively, on $k$ vertices. We give necessary and sufficient conditions for the existence of a complete ${P_{5}, S_{5}}$ -decomposition of Cartesian product of complete graphs.

4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi (2017)

Czechoslovak Mathematical Journal

Similarity:

A $(0, 2)$ -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0, λ)$ -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0, 2)$ -graph. $(0, 2)$ -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0, λ)$ -graphs and more specifically...

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_{f}$ of all finite undirected graphs. If G is a graph from $C_{f}$ , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

Similarity:

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} (v)$ 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 ${r a d}_{X} G$ of $G$ ...