Currently displaying 1 – 20 of 20

Showing per page

Order by Relevance | Title | Year of publication

Sums of Powered Characteristic Roots Count Distance-Independent Circular Sets

Zdzisław Skupień — 2013

Discussiones Mathematicae Graph Theory

Significant values of a combinatorial count need not fit the recurrence for the count. Consequently, initial values of the count can much outnumber those for the recurrence. So is the case of the count, Gl(n), of distance-l independent sets on the cycle Cn, studied by Comtet for l ≥ 0 and n ≥ 1 [sic]. We prove that values of Gl(n) are nth power sums of the characteristic roots of the corresponding recurrence unless 2 ≤ n ≤ l. Lucas numbers L(n) are thus generalized since L(n) is the count in question...

Some maximum multigraphs and edge/vertex distance colourings

Zdzisław Skupień — 1995

Discussiones Mathematicae Graph Theory

Shannon-Vizing-type problems concerning the upper bound for a distance chromatic index of multigraphs G in terms of the maximum degree Δ(G) are studied. Conjectures generalizing those related to the strong chromatic index are presented. The chromatic d-index and chromatic d-number of paths, cycles, trees and some hypercubes are determined. Among hypercubes, however, the exact order of their growth is found.

Decompositions into two paths

Zdzisław Skupień — 2005

Discussiones Mathematicae Graph Theory

It is proved that a connected multigraph G which is the union of two edge-disjoint paths has another decomposition into two paths with the same set, U, of endvertices provided that the multigraph is neither a path nor cycle. Moreover, then the number of such decompositions is proved to be even unless the number is three, which occurs exactly if G is a tree homeomorphic with graph of either symbol + or ⊥. A multigraph on n vertices with exactly two traceable pairs is constructed for each n ≥ 3. The...

Decompositions of nearly complete digraphs into t isomorphic parts

Mariusz MeszkaZdzisław Skupień — 2009

Discussiones Mathematicae Graph Theory

An arc decomposition of the complete digraph Kₙ into t isomorphic subdigraphs is generalized to the case where the numerical divisibility condition is not satisfied. Two sets of nearly tth parts are constructively proved to be nonempty. These are the floor tth class ( Kₙ-R)/t and the ceiling tth class ( Kₙ+S)/t, where R and S comprise (possibly copies of) arcs whose number is the smallest possible. The existence of cyclically 1-generated decompositions of Kₙ into cycles C n - 1 and into paths P is characterized....

Decompositions of a complete multidigraph into almost arbitrary paths

Mariusz MeszkaZdzisław Skupień — 2012

Discussiones Mathematicae Graph Theory

For n ≥ 4, the complete n-vertex multidigraph with arc multiplicity λ is proved to have a decomposition into directed paths of arbitrarily prescribed lengths ≤ n - 1 and different from n - 2, unless n = 5, λ = 1, and all lengths are to be n - 1 = 4. For λ = 1, a more general decomposition exists; namely, up to five paths of length n - 2 can also be prescribed.

Counting Maximal Distance-Independent Sets in Grid Graphs

Reinhardt EulerPaweł OleksikZdzisław Skupień — 2013

Discussiones Mathematicae Graph Theory

Previous work on counting maximal independent sets for paths and certain 2-dimensional grids is extended in two directions: 3-dimensional grid graphs are included and, for some/any ℓ ∈ N, maximal distance-ℓ independent (or simply: maximal ℓ-independent) sets are counted for some grids. The transfer matrix method has been adapted and successfully applied

On traceability and 2-factors in claw-free graphs

Dalibor FrončekZdeněk RyjáčekZdzisław Skupień — 2004

Discussiones Mathematicae Graph Theory

If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σₖ > n + k² - 4k + 7 (where k is an arbitrary constant), then G has a 2-factor with at most k - 1 components. As a second main result, we present classes of graphs ₁,...,₈ such that every sufficiently large connected claw-free graph satisfying degree condition σ₆(k) > n + 19 (or, as a corollary, δ(G) > (n+19)/6) either belongs to i = 1 i or is traceable.

Decompositions of multigraphs into parts with two edges

Jaroslav IvančoMariusz MeszkaZdzisław Skupień — 2002

Discussiones Mathematicae Graph Theory

Given a family 𝓕 of multigraphs without isolated vertices, a multigraph M is called 𝓕-decomposable if M is an edge disjoint union of multigraphs each of which is isomorphic to a member of 𝓕. We present necessary and sufficient conditions for the existence of such decompositions if 𝓕 comprises two multigraphs from the set consisting of a 2-cycle, a 2-matching and a path with two edges.

Applied Graph Theory III. Euler and Hamilton graphs. Salesman problem.

Maciej M. SysłoZdzisław Skupień — 1977

Mathematica Applicanda

A survey of some possible applications of graph theory to numerical analysis is given in part III. They are the following: (1) application of optimal trees to estimating the error in addition processes of positive floating-point numbers, (2) application of graphs to solving systems of linear equations, and (3) application of graphs in rearranging matrices to an easier-to-handle form.

A Sokoban-type game and arc deletion within irregular digraphs of all sizes

Zyta Dziechcińska-HalamodaZofia MajcherJerzy MichaelZdzisław Skupień — 2007

Discussiones Mathematicae Graph Theory

Digraphs in which ordered pairs of out- and in-degrees of vertices are mutually distinct are called irregular, see Gargano et al. [3]. Our investigations focus on the problem: what are possible sizes of irregular digraphs (oriented graphs) for a given order n? We show that those sizes in both cases make up integer intervals. The extremal sizes (the endpoints of these intervals) are found in [1,5]. In this paper we construct, with help of Sokoban-type game, n-vertex irregular oriented graphs (irregular...

Extremum degree sets of irregular oriented graphs and pseudodigraphs

Zyta Dziechcińska-HalamodaZofia MajcherJerzy MichaelZdzisław Skupień — 2006

Discussiones Mathematicae Graph Theory

A digraph in which any two vertices have distinct degree pairs is called irregular. Sets of degree pairs for all irregular oriented graphs (also loopless digraphs and pseudodigraphs) with minimum and maximum size are determined. Moreover, a method of constructing corresponding irregular realizations of those sets is given.

On extremal sizes of locally k -tree graphs

Mieczysław BorowieckiPiotr BorowieckiElżbieta SidorowiczZdzisław Skupień — 2010

Czechoslovak Mathematical Journal

A graph G is a if for any vertex v the subgraph induced by the neighbours of v is a k -tree, k 0 , where 0 -tree is an edgeless graph, 1 -tree is a tree. We characterize the minimum-size locally k -trees with n vertices. The minimum-size connected locally k -trees are simply ( k + 1 ) -trees. For k 1 , we construct locally k -trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n -vertex locally k -tree graph is between Ω ( n ) and O ( n 2 ) , where both bounds are asymptotically...

Page 1 Next

Download Results (CSV)