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: 9

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

Wyniki wyszukiwania

help Sortuj według:

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

γ-Cycles In Arc-Colored Digraphs

100%
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.
2
Content available remote

Some Results on 4-Transitive Digraphs

100%
García-Vázquez P. R., Hernández-Cruz C.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
117-129
EN
Let D be a digraph with set of vertices V and set of arcs A. We say that D is k-transitive if for every pair of vertices u, v ∈ V, the existence of a uv-path of length k in D implies that (u, v) ∈ A. A 2-transitive digraph is a transitive digraph in the usual sense. A subset N of V is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V \ N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V. The problem of determining whether a digraph has a k-kernel is known to be 𝒩𝒫-complete for every k ≥ 2. In this work, we characterize 4-transitive digraphs having a 3-kernel and also 4-transitive digraphs having a 2-kernel. Using the latter result, a proof of the Laborde-Payan-Xuong conjecture for 4-transitive digraphs is given. This conjecture establishes that for every digraph D, an independent set can be found such that it intersects every longest path in D. Also, Seymour’s Second Neighborhood Conjecture is verified for 4-transitive digraphs and further problems are proposed.
3
Content available remote

A new bound for the spectral radius of Brualdi-Li matrices

100%
Chen X.
Special Matrices
|
2015
|
tom 3
|
nr 1
EN
Let B2m denote the Brualdi-Li matrix of order 2m, and let ρ2m = ρ(B2m ) denote the spectral radius of the Brualdi-Li Matrix. Then [...] . where m > 2, e = 2.71828 · · · , [...] and [...] .
4
Content available remote

On kernels by monochromatic paths in the corona of digraphs

100%
Włoch I.
Open Mathematics
|
2008
|
tom 6
|
nr 4
537-542
EN
In this paper we derive necessary and sufficient conditions for the existence of kernels by monochromatic paths in the corona of digraphs. Using these results, we are able to prove the main result of this paper which provides necessary and sufficient conditions for the corona of digraphs to be monochromatic kernel-perfect. Moreover we calculate the total numbers of kernels by monochromatic paths, independent by monochromatic paths sets and dominating by monochromatic paths sets in this digraphs product.
5
Content available remote

Products Of Digraphs And Their Competition Graphs

81%
Sonntag M., Teichert H.-M.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
43-58
EN
If D = (V, A) is a digraph, its competition graph (with loops) CGl(D) has the vertex set V and {u, v} ⊆ V is an edge of CGl(D) if and only if there is a vertex w ∈ V such that (u, w), (v, w) ∈ A. In CGl(D), loops {v} are allowed only if v is the only predecessor of a certain vertex w ∈ V. For several products D1 ⚬ D2 of digraphs D1 and D2, we investigate the relations between the competition graphs of the factors D1, D2 and the competition graph of their product D1 ⚬ D2.
6
Content available remote

The Dichromatic Number of Infinite Families of Circulant Tournaments

81%
Javier N., Llano B.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
221-238
EN
The dichromatic number dc(D) of a digraph D is defined to be the minimum number of colors such that the vertices of D can be colored in such a way that every chromatic class induces an acyclic subdigraph in D. The cyclic circulant tournament is denoted by [...] T=C→2n+1(1,2,…,n) $T = \overrightarrow C _{2n + 1} (1,2, \ldots ,n)$ , where V (T) = ℤ2n+1 and for every jump j ∈ {1, 2, . . . , n} there exist the arcs (a, a + j) for every a ∈ ℤ2n+1. Consider the circulant tournament [...] C→2n+1〈k〉 $\overrightarrow C _{2n + 1} \left\langle k \right\rangle $ obtained from the cyclic tournament by reversing one of its jumps, that is, [...] C→2n+1 〈k〉 $\overrightarrow C _{2n + 1} \left\langle k \right\rangle $ has the same arc set as [...] C→2n+1(1,2,…,n) $\overrightarrow C _{2n + 1} (1,2, \ldots ,n)$ except for j = k in which case, the arcs are (a, a − k) for every a ∈ ℤ2n+1. In this paper, we prove that [...] dc(C→2n+1 〈k〉)∈{2,3,4} $dc ( {\overrightarrow C _{2n + 1} \left\langle k \right\rangle } ) \in \{ 2,3,4\}$ for every k ∈ {1, 2, . . . , n}. Moreover, we classify which circulant tournaments [...] C→2n+1 〈k〉 $\overrightarrow C _{2n + 1} \left\langle k \right\rangle$ are vertex-critical r-dichromatic for every k ∈ {1, 2, . . . , n} and r ∈ {2, 3, 4}. Some previous results by Neumann-Lara are generalized.
7
Content available remote

Signed Total Roman Domination in Digraphs

81%
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.
8
Content available remote

The signed k-domination number of directed graphs

62%
Atapour M., Sheikholeslami S., Hajypory R., Volkmann L.
Open Mathematics
|
2010
|
tom 8
|
nr 6
1048-1057
EN
Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d D− ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N −[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $$ \sum\nolimits_{v \in V} {f(v)} $$. The signed k-domination number for a digraph D is γkS(D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γkS(D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.
9
Content available remote

On characteristic and permanent polynomials of a matrix

62%
Singh R., Bapat R. B.
Special Matrices
|
2017
|
tom 5
|
nr 1
97-112
EN
There is a digraph corresponding to every square matrix over ℂ. We generate a recurrence relation using the Laplace expansion to calculate the characteristic and the permanent polynomials of a square matrix. Solving this recurrence relation, we found that the characteristic and the permanent polynomials can be calculated in terms of the characteristic and the permanent polynomials of some specific induced subdigraphs of blocks in the digraph, respectively. Interestingly, these induced subdigraphs are vertex-disjoint and they partition the digraph. Similar to the characteristic and the permanent polynomials; the determinant and the permanent can also be calculated. Therefore, this article provides a combinatorial meaning of these useful quantities of the matrix theory. We conclude this article with a number of open problems which may be attempted for further research in this direction.
first rewind previous Strona / 1 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ć.