Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 23

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  digraph
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available remote

Sharp Upper Bounds on the Signless Laplacian Spectral Radius of Strongly Connected Digraphs

100%
Xi W., Wang L.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
977-988
EN
Let G = (V (G),E(G)) be a simple strongly connected digraph and q(G) be the signless Laplacian spectral radius of G. For any vertex vi ∈ V (G), let d+i denote the outdegree of vi, m+i denote the average 2-outdegree of vi, and N+i denote the set of out-neighbors of vi. In this paper, we prove that: (1) (1) q(G) = d+1 +d+2 , (d+1 ≠ d+2) if and only if G is a star digraph [...] ,where d+1, d+2 are the maximum and the second maximum outdegree, respectively [...] is the digraph on n vertices obtained from a star graph K1,n−1 by replacing each edge with a pair of oppositely directed arcs). (2) [...] with equality if and only if G is a regular digraph. (3) [...] Moreover, the equality holds if and only if G is a regular digraph or a bipartite semiregular digraph. (4) [...] . If the equality holds, then G is a regular digraph or G ∈Ω, where is a class of digraphs defined in this paper.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A sufficient condition for the existence of k-kernels in digraphs

80%
Galeana-Sánchez H., Rincón-Mejía H.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 2
197-204
EN
In this paper, we prove the following sufficient condition for the existence of k-kernels in digraphs: Let D be a digraph whose asymmetrical part is strongly conneted and such that every directed triangle has at least two symmetrical arcs. If every directed cycle γ of D with l(γ) ≢ 0 (mod k), k ≥ 2 satisfies at least one of the following properties: (a) γ has two symmetrical arcs, (b) γ has four short chords. Then D has a k-kernel. This result generalizes some previous results on the existence of kernels and k-kernels in digraphs. In particular, it generalizes the following Theorem of M. Kwaśnik [5]: Let D be a strongly connected digraph, if every directed cycle of D has length ≡ 0 (mod k), k ≥ 2. Then D has a k-kernel.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Radii and centers in iterated line digraphs

80%
Knor M., Niepel L. u.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 1
17-26
EN
We show that the out-radius and the radius grow linearly, or "almost" linearly, in iterated line digraphs. Further, iterated line digraphs with a prescribed out-center, or a center, are constructed. It is shown that not every line digraph is admissible as an out-center of line digraph.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A proof of menger's theorem by contraction

80%
Göring F.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
111-112
EN
A short proof of the classical theorem of Menger concerning the number of disjoint AB-paths of a finite graph for two subsets A and B of its vertex set is given. The main idea of the proof is to contract an edge of the graph.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Degree sequences of digraphs with highly irregular property

80%
Majcher Z., Michael J.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
49-61
EN
A digraph such that for each its vertex, vertices of the out-neighbourhood have different in-degrees and vertices of the in-neighbourhood have different out-degrees, will be called an HI-digraph. In this paper, we give a characterization of sequences of pairs of out- and in-degrees of HI-digraphs.
6
Content available remote

γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs

80%
Casas-Bautista E., Galeana-Sánchez H., Rojas-Monroy R.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
493-507
EN
We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. If D is an m-coloured digraph and a ∈ A(D), colour(a) will denote the colour has been used on a. A path (or a cycle) is called monochromatic if all of its arcs are coloured alike. A γ-cycle in D is a sequence of vertices, say γ = (u0, u1, . . . , un), such that ui ≠ uj if i ≠ j and for every i ∈ {0, 1, . . . , n} there is a uiui+1-monochromatic path in D and there is no ui+1ui-monochromatic path in D (the indices of the vertices will be taken mod n+1). A set N ⊆ V (D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u, v ∈ N there is no monochromatic path between them and; (ii) for every vertex x ∈ V (D) \ N there is a vertex y ∈ N such that there is an xy-monochromatic path. Let D be a finite m-coloured digraph. Suppose that {C1,C2} is a partition of C, the set of colours of D, and Di will be the spanning subdigraph of D such that A(Di) = {a ∈ A(D) | colour(a) ∈ Ci}. In this paper, we give some sufficient conditions for the existence of a kernel by monochromatic paths in a digraph with the structure mentioned above. In particular we obtain an extension of the original result by B. Sands, N. Sauer and R. Woodrow that asserts: Every 2-coloured digraph has a kernel by monochromatic paths. Also, we extend other results obtained before where it is proved that under some conditions an m-coloured digraph has no γ-cycles.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On independent sets and non-augmentable paths in directed graphs

80%
Galeana-Sánchez H.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 2
171-181
EN
We investigate sufficient conditions, and in case that D be an asymmetrical digraph a necessary and sufficient condition for a digraph to have the following property: "In any induced subdigraph H of D, every maximal independent set meets every non-augmentable path". Also we obtain a necessary and sufficient condition for any orientation of a graph G results a digraph with the above property. The property studied in this paper is an instance of the property of a conjecture of J.M. Laborde, Ch. Payan and N.H. Huang: "Every digraph contains an independent set which meets every longest directed path" (1982).
8
Content available remote

γ-Cycles In Arc-Colored Digraphs

80%
Galeana-Sánchez H., Gaytán-Gómez G., Rojas-Monroy R.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
103-116
EN
We call a digraph D an m-colored digraph if the arcs of D are colored with m colors. A directed path (or a directed cycle) is called monochromatic if all of its arcs are colored alike. A subdigraph H in D is called rainbow if all of its arcs have different colors. A set N ⊆ V (D) is said to be a kernel by monochromatic paths of D if it satisfies the two following conditions: for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, and for every vertex x ∈ V (D) − N there is a vertex y ∈ N such that there is an xy-monochromatic path in D. A γ-cycle in D is a sequence of different vertices γ = (u0, u1, . . . , un, u0) such that for every i ∈ {0, 1, . . . , n}: there is a uiui+1-monochromatic path, and there is no ui+1ui-monochromatic path. The addition over the indices of the vertices of γ is taken modulo (n + 1). If D is an m-colored digraph, then the closure of D, denoted by ℭ(D), is the m-colored multidigraph defined as follows: V (ℭ (D)) = V (D), A(ℭ (D)) = A(D) ∪ {(u, v) with color i | there exists a uv-monochromatic path colored i contained in D}. In this work, we prove the following result. Let D be a finite m-colored digraph which satisfies that there is a partition C = C1 ∪ C2 of the set of colors of D such that: D[Ĉi] (the subdigraph spanned by the arcs with colors in Ci) contains no γ-cycles for i ∈ {1, 2}; If ℭ (D) contains a rainbow C3 = (x0, z, w, x0) involving colors of C1 and C2, then (x0, w) ∈ A(ℭ (D)) or (z, x0) ∈ A(ℭ (D)); If ℭ (D) contains a rainbow P3 = (u, z, w, x0) involving colors of C1 and C2, then at least one of the following pairs of vertices is an arc in ℭ (D): (u, w), (w, u), (x0, u), (u, x0), (x0, w), (z, u), (z, x0). Then D has a kernel by monochromatic paths. This theorem can be applied to all those digraphs that contain no γ-cycles. Generalizations of many previous results are obtained as a direct consequence of this theorem.
9
Content available remote

On the Hypercompetition Numbers of Hypergraphs with Maximum Degree at Most Two

80%
Sano Y.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 3
595-598
EN
In this note, we give an easy and short proof for the theorem by Park and Kim stating that the hypercompetition numbers of hypergraphs with maximum degree at most two is at most two.
10
Content available remote

(K − 1)-Kernels In Strong K-Transitive Digraphs

80%
Wang R.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
229-235
EN
Let D = (V (D),A(D)) be a digraph and k ≥ 2 be an integer. A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v) ≥ k; it is l-absorbent if for every u ∈ V (D) − N, there exists v ∈ N such that d(u, v) ≤ l. A (k, l)-kernel of D is a k-independent and l-absorbent subset of V (D). A k-kernel is a (k, k − 1)-kernel. A digraph D is k-transitive if for any path x0x1 ・ ・ ・ xk of length k, x0 dominates xk. Hernández-Cruz [3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219] proved that a 3-transitive digraph has a 2-kernel if and only if it has no terminal strong component isomorphic to a 3-cycle. In this paper, we generalize the result to strong k-transitive digraphs and prove that a strong k-transitive digraph with k ≥ 4 has a (k − 1)-kernel if and only if it is not isomorphic to a k-cycle.
11
Content available remote

The k-Rainbow Bondage Number of a Digraph

80%
Amjadi J., Mohammadi N., Sheikholeslami S. M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
261-270
EN
Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF of D. The k-rainbow bondage number brk(D) of a digraph D with maximum in-degree at least two, is the minimum cardinality of all sets A′ ⊆ A for which γrk(D−A′) > γrk(D). In this paper, we establish some bounds for the k-rainbow bondage number and determine the k-rainbow bondage number of several classes of digraphs.
12
Content available remote

Signed Total Roman Domination in Digraphs

80%
Volkmann L.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
261-272
EN
Let D be a finite and simple digraph with vertex set V (D). A signed total Roman dominating function (STRDF) on a digraph D is a function f : V (D) → {−1, 1, 2} satisfying the conditions that (i) ∑x∈N−(v) f(x) ≥ 1 for each v ∈ V (D), where N−(v) consists of all vertices of D from which arcs go into v, and (ii) every vertex u for which f(u) = −1 has an inner neighbor v for which f(v) = 2. The weight of an STRDF f is w(f) = ∑v∈V (D) f(v). The signed total Roman domination number γstR(D) of D is the minimum weight of an STRDF on D. In this paper we initiate the study of the signed total Roman domination number of digraphs, and we present different bounds on γstR(D). In addition, we determine the signed total Roman domination number of some classes of digraphs. Some of our results are extensions of known properties of the signed total Roman domination number γstR(G) of graphs G.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The Laplacian spectrum of some digraphs obtained from the wheel

80%
Su L., Li H.-H., Zheng L.-R.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
255-261
EN
The problem of distinguishing, in terms of graph topology, digraphs with real and partially non-real Laplacian spectra is important for applications. Motivated by the question posed in [R. Agaev, P. Chebotarev, Which digraphs with rings structure are essentially cyclic?, Adv. in Appl. Math. 45 (2010), 232-251], in this paper we completely list the Laplacian eigenvalues of some digraphs obtained from the wheel digraph by deleting some arcs.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The total {k}-domatic number of digraphs

80%
Sheikholeslami S., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 3
461-471
EN
For a positive integer k, a total {k}-dominating function of a digraph D is a function f from the vertex set V(D) to the set {0,1,2, ...,k} such that for any vertex v ∈ V(D), the condition $∑_{u ∈ N^{ -}(v)}f(u) ≥ k$ is fulfilled, where N¯(v) consists of all vertices of D from which arcs go into v. A set ${f₁,f₂, ...,f_d}$ of total {k}-dominating functions of D with the property that $∑_{i = 1}^d f_i(v) ≤ k$ for each v ∈ V(D), is called a total {k}-dominating family (of functions) on D. The maximum number of functions in a total {k}-dominating family on D is the total {k}-domatic number of D, denoted by $dₜ^{{k}}(D)$. Note that $dₜ^{{1}}(D)$ is the classic total domatic number $dₜ(D)$. In this paper we initiate the study of the total {k}-domatic number in digraphs, and we present some bounds for $dₜ^{{k}}(D)$. Some of our results are extensions of well-know properties of the total domatic number of digraphs and the total {k}-domatic number of graphs.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The directed path partition conjecture

71%
Frick M., van Aardt S., Dlamini G., Dunbar J., Oellermann O.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
331-343
EN
The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = a+b, there exists a vertex partition (A,B) of D such that no path in D⟨A⟩ has more than a vertices and no path in D⟨B⟩ has more than b vertices. We develop methods for finding the desired partitions for various classes of digraphs.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Signed domination and signed domatic numbers of digraphs

71%
Volkmann L.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
415-427
EN
Let D be a finite and simple digraph with the vertex set V(D), and let f:V(D) → {-1,1} be a two-valued function. If $∑_{x ∈ N¯[v]}f(x) ≥ 1$ for each v ∈ V(D), where N¯[v] consists of v and all vertices of D from which arcs go into v, then f is a signed dominating function on D. The sum f(V(D)) is called the weight w(f) of f. The minimum of weights w(f), taken over all signed dominating functions f on D, is the signed domination number $γ_S(D)$ of D. A set ${f₁,f₂,...,f_d}$ of signed dominating functions on D with the property that $∑_{i = 1}^d f_i(x) ≤ 1$ for each x ∈ V(D), is called a signed dominating family (of functions) on D. The maximum number of functions in a signed dominating family on D is the signed domatic number of D, denoted by $d_S(D)$. In this work we show that $4-n ≤ γ_S(D) ≤ n$ for each digraph D of order n ≥ 2, and we characterize the digraphs attending the lower bound as well as the upper bound. Furthermore, we prove that $γ_S(D) + d_S(D) ≤ n + 1$ for any digraph D of order n, and we characterize the digraphs D with $γ_S(D) + d_S(D) = n + 1$. Some of our theorems imply well-known results on the signed domination number of graphs.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Cyclically k-partite digraphs and k-kernels

71%
Galeana-Sánchez H., Hernández-Cruz C.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
63-78
EN
Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N then d(u,v) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. A digraph D is cyclically k-partite if there exists a partition ${V_i}_{i = 0}^{k-1}$ of V(D) such that every arc in D is a $V_i V_{i+1}-arc$ (mod k). We give a characterization for an unilateral digraph to be cyclically k-partite through the lengths of directed cycles and directed cycles with one obstruction, in addition we prove that such digraphs always have a k-kernel. A study of some structural properties of cyclically k-partite digraphs is made which bring interesting consequences, e.g., sufficient conditions for a digraph to have k-kernel; a generalization of the well known and important theorem that states if every cycle of a graph G has even length, then G is bipartite (cyclically 2-partite), we prove that if every cycle of a graph G has length ≡ 0 (mod k) then G is cyclically k-partite; and a generalization of another well known result about bipartite digraphs, a strong digraph D is bipartite if and only if every directed cycle has even length, we prove that an unilateral digraph D is bipartite if and only if every directed cycle with at most one obstruction has even length.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On uniquely partitionable relational structures and object systems

71%
Bucko J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
281-289
EN
We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = {A₁,A₂,...,Aₘ} is a finite set of the objects of C, such that the ground-set $V(A_i)$ of each object $A_i ∈ E$ is a finite set with at least two elements and $V ⊇ ⋃_{i=1}^m V(A_i)$. To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary property of simple object systems over a category C is any class of systems closed under isomorphism, induced-subsystems and disjoint union of systems, respectively. We present a survey of recent results and conditions for object systems to be uniquely partitionable into subsystems of given properties.
19
Content available remote

4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs

61%
Hernández-Cruz C.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
247-260
EN
Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is transitive if for every three distinct vertices u, v,w ∈ V (D), (u, v), (v,w) ∈ A(D) implies that (u,w) ∈ A(D). This concept can be generalized as follows: A digraph is k-transitive if for every u, v ∈ V (D), the existence of a uv-directed path of length k in D implies that (u, v) ∈ A(D). A very useful structural characterization of transitive digraphs has been known for a long time, and recently, 3-transitive digraphs have been characterized. In this work, some general structural results are proved for k-transitive digraphs with arbitrary k ≥ 2. Some of this results are used to characterize the family of 4-transitive digraphs. Also some of the general results remain valid for k-quasi-transitive digraphs considering an additional hypothesis. A conjecture on a structural property of k-transitive digraphs is proposed.
20
Content available remote

Some Remarks On The Structure Of Strong K-Transitive Digraphs

61%
Hernández-Cruz C., Montellano-Ballesteros J. J.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 4
651-671
EN
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 that in most cases, such digraphs are complete digraphs or cycle extensions. Also, the obtained results are used to prove some particular cases of the Laborde-Payan-Xuong Conjecture.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.