EuDML | Browse

An infinite family of T-factorizations of complete graphs $K_{2 n}$ , where 2n = 56k and k is a positive integer, in which the set of vertices of T can be split into two subsets of the same cardinality such that degree sums of vertices in both subsets are not equal, is presented. The existence of such T-factorizations provides a negative answer to the problem posed by Kubesa.

Some cyclic solutions to the three table Oberwolfach problem.

Ollis, M.A. (2005)

The Electronic Journal of Combinatorics [electronic only]

Some recent results on domination in graphs

Michael D. Plummer (2006)

Discussiones Mathematicae Graph Theory

In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; (3) upper bounds...

Some Relations for Graphic Polynomials

Ivan Gutman (1986)

Publications de l'Institut Mathématique

Some remarks on domatic numbers of graphs

Bohdan Zelinka (1981)

Časopis pro pěstování matematiky

Splitting Cubic Circle Graphs

Lorenzo Traldi (2016)

Discussiones Mathematicae Graph Theory

We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.

Star number and star arboricity of a complete multigraph

Chiang Lin, Tay-Woei Shyu (2006)

Czechoslovak Mathematical Journal

Let $G$ be a multigraph. The star number $s (G)$ of $G$ is the minimum number of stars needed to decompose the edges of $G$ . The star arboricity $s a (G)$ of $G$ is the minimum number of star forests needed to decompose the edges of $G$ . As usual $λ K_{n}$ denote the $λ$ -fold complete graph on $n$ vertices (i.e., the multigraph on $n$ vertices such that there are $λ$ edges between every pair of vertices). In this paper, we prove that for $n \geq 2$ $...$

Star-Cycle Factors of Graphs

Yoshimi Egawa, Mikio Kano, Zheng Yan (2014)

Discussiones Mathematicae Graph Theory

A spanning subgraph F of a graph G is called a star-cycle factor of G if each component of F is a star or cycle. Let G be a graph and f : V (G) → {1, 2, 3, . . .} be a function. Let W = {v ∈ V (G) : f(v) = 1}. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor F with the property that (i) if a component D of F is a star with center v, then degF (v) ≤ f(v), and (ii) if a component D of F is a cycle, then V (D) ⊆ W if and only if iso(G − S) ≤ Σx∈S f(x) for all...

Strong Transfinite Version of König's Duality Theorem.

R.A. Brualdi (1971)

Monatshefte für Mathematik

Strong ƒ-Star Factors of Graphs

Zheng Yan (2015)

Discussiones Mathematicae Graph Theory

Let G be a graph and f : V (G) → {2, 3, . . .}. A spanning subgraph F is called strong f-star of G if each component of F is a star whose center x satisfies degF (x) ≤ ƒ(x) and F is an induced subgraph of G. In this paper, we prove that G has a strong f-star factor if and only if oddca(G − S) ≤ ∑x∊S ƒ(x) for all S ⊂ V (G), where oddca(G) denotes the number of odd complete-cacti of G.

Strongly maximal matchings in infinite graphs.

Aharoni, Ron, Berger, Eli, Georgakopoulos, Agelos, Sprussel, Philipp (2008)

The Electronic Journal of Combinatorics [electronic only]

Symmetric Hamilton Cycle Decompositions of Complete Multigraphs

V. Chitra, A. Muthusamy (2013)

Discussiones Mathematicae Graph Theory

Let n ≥ 3 and ⋋ ≥ 1 be integers. Let ⋋Kn denote the complete multigraph with edge-multiplicity ⋋. In this paper, we show that there exists a symmetric Hamilton cycle decomposition of ⋋K2m for all even ⋋ ≥ 2 and m ≥ 2. Also we show that there exists a symmetric Hamilton cycle decomposition of ⋋K2m − F for all odd ⋋ ≥ 3 and m ≥ 2. In fact, our results together with the earlier results (by Walecki and Brualdi and Schroeder) completely settle the existence of symmetric Hamilton cycle decomposition of...

Teorie grafů, 1736–1963 [Book]

Šišma, Pavel (1997)

The Balanced Decomposition Number of TK4 and Series-Parallel Graphs

Shinya Fujita, Henry Liu (2013)

Discussiones Mathematicae Graph Theory

A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪˙ · · · ∪˙ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G)...

The B-Domatic Number of a Graph

Odile Favaron (2013)

Discussiones Mathematicae Graph Theory

Besides the classical chromatic and achromatic numbers of a graph related to minimum or minimal vertex partitions into independent sets, the b-chromatic number was introduced in 1998 thanks to an alternative definition of the minimality of such partitions. When independent sets are replaced by dominating sets, the parameters corresponding to the chromatic and achromatic numbers are the domatic and adomatic numbers d(G) and ad(G). We introduce the b-domatic number bd(G) as the counterpart of the...

The bigraph decomposition number of a graph

Bohdan Zelinka (1988)

Časopis pro pěstování matematiky

Currently displaying 381 – 400 of 455

Previous Page 20 Next