Wyniki wyszukiwania - Biblioteka Nauki

1

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

On arc-coloring of digraphs

100%

Zwonek M.

|

tom Vol. 26, no. 1

185-195

EN

In the paper we deal with the problem of the arc-colouring of some classes of digraphs (tournaments, complete digraphs and products of digraphs).

3

Digraph description of k-interchange technique for optimization over permutations and adaptive algorithm system

80%

Levin M. S.

|

tom Vol. 26, No. 3

225-235

EN

The paper describes a general glance to the use of element exchange techniques for optimization over permutations. A multi-level description of problems is proposed which is a fundamental to understand nature and complexity of optimization problems over permutations (e.g., ordering, scheduling, traveling salesman problem). The description is based on permutation neighborhoods of several kinds (e.g., by improvement of an objective function). Our proposed operational digraph and its kinds can be considered as a way to understand convexity and polynomial solvability for combinatorial optimization problems over permutations. Issues of an analysis of problems and a design of hierarchical heuristics are discussed. The discussion leads to a multi-level adaptive algorithm system which analyzes an individual problem and selects / designs a solving strategy (trajectory).

4

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

80%

Casas-Bautista E. , Galeana-Sánchez H. , Rojas-Monroy R.

|

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.

5

Toward Wojda's conjecture on digraph packing

80%

Konarski J. , Żak A.

Opuscula Mathematica

|

2017

|

tom Vol. 37, no. 4

589--595

EN

Given a positive integer m ≤ n/2, Wojda conjectured in 1985 that if D1 and D2 are digraphs of order n such that [formula] and [formula] then D1 and D2 pack. The cases when m = 1 or m = n/2 follow from known results. Here we prove the conjecture for [formula].

6

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

80%

Wang R.

|

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.

7

The k-Rainbow Bondage Number of a Digraph

80%

Amjadi J. , Mohammadi N. , Sheikholeslami S. M. , Volkmann L.

|

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.

8

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

80%

Sano Y.

|

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.

9

γ-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.

10

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.

11

Power on digraphs

80%

Peters H. , Timmer J. , van den Brink R.

|

2016

|

tom Vol. 26, No. 2

107--125

EN

It is assumed that relations between n players are represented by a directed graph or digraph. Such a digraph is called invariant if there is a link (arc) between any two players between whom there is also a directed path. We characterize a class of power indices for invariant digraphs based on four axioms: Null player, Constant sum, Anonymity, and the Transfer property. This class is determined by 2n – 2 parameters. By considering additional conditions about the effect of adding a directed link between two players, we single out three different, one-parameter families of power indices, reflecting several well- -known indices from the literature: the Copeland score, β- and apex type indices.

12

Power on digraphs

80%

PETERS H. , TIMMER J. , VAN DEN BRINK R.

|

2016

|

tom 26

|

nr 2

107-125

EN

It is assumed that relations between n players are represented by a directed graph or digraph. Such a digraph is called invariant if there is a link (arc) between any two players between whom there is also a directed path. We characterize a class of power indices for invariant digraphs based on four axioms: Null player, Constant sum, Anonymity, and the Transfer property. This class is determined by 2n – 2 parameters. By considering additional conditions about the effect of adding a directed link between two players, we single out three different, one-parameter families of power indices, reflecting several well- -known indices from the literature: the Copeland score, - and apex type indices.

13

Large minimal irregular digraphs

80%

Dziechcińska-Halamoda Z. , Majcher Z. , Michael J. , Skupień Z.

Opuscula Mathematica

|

2003

|

tom Vol. 23

21-24

EN

A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal if the removal of any arc results in a non-irregular digraph. A large minimal irregular digraph Fn of order n is constructed if n is the sum of initial positive integers. It is easily seen that the minimum and maximum sizes among n-vertex irregular digraphs are asymptotic to [formula] and n2, respectively. It appears that the size of Fn is asymptotic to n2, too. Similarly, a minimal irregular oriented graph Hn is constructed such that the size of Hn is asymptotic to 1/2n2 whence it is asymptotically the largest size among n-vertex oriented graphs whether irregular or not.

14

Rough Set Theory and Digraphs

80%

Chiaselotti G. , Ciucci D. , Gentile T. , Infusino F.

|

tom Vol. 153, nr 4

291--325

EN

In this paper we apply rough set theory to information tables induced from finite directed graphs without loops and multiples arcs (digraphs). Specifically, we use the adjacency matrix of a digraph as a particular type of information table. In this way, we are able to explore on digraphs the notions of indiscernibility partitions, lower and upper approximations, generalized core, reducts and discernibility matrix. All these ideas will be exemplified on standard digraph families as well on examples from social networks and patterns of flight routes between airports.

15

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

60%

Hernández-Cruz C.

|

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.

16

Some Remarks On The Structure Of Strong K-Transitive Digraphs

60%

Hernández-Cruz C. , Montellano-Ballesteros J. J.

|

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.

17

The Complete Set of Distinguishable Diagnostic States for a Centrifugal Pump System

51%

Szczepański P. , Kijak R.

Problemy Mechatroniki : uzbrojenie, lotnictwo, inżynieria bezpieczeństwa

|

2023

|

tom Vol. 14, Nr 3 (53)

95--118

EN

In this article, the concept of determination of a complete set of distinguishable diagnostic states has been utilised, which has been well known since the 1980’s and, in essence, could refer to any item with any application and any structural features. The only condition set for this item, is its ability to be described by a structure consisting of single exit-point elements. As a consequence, it can become possible to assess, amongst other things, its layers, strong cohesions, transitive and antitransitive closures. Typical tools of such assessment are matrices: transition and reachability. The reason that a centrifugal pump has been selected is not only its importance and common use, but also specifics of interaction of its elements. It is possible to identify for them: independence, dependence, and interdependence. For particular distinguishable diagnostic states, the probabilities of its occurrence have been determined. These probabilities have become a starting point to estimate structure entropy and intensity of transition from the health to any particular failure state. Results of such estimation have been depicted by relevant graphs. A reference has been made to the Bayesian methods and the inseparable ‘serial reliability structure’, to identify their flaws that result particularly from simplifications leading to false and ambiguous diagnoses. The probabilities of health for particular elements have been differentiated by the selection of adequate Weibull indices.

PL

W artykule posłużono się, znaną od lat osiemdziesiątych ubiegłego wieku, koncepcją wyznaczania pełnego zbioru rozróżnialnych stanów diagnostycznych, która w istocie rzeczy może odnieść się do dowolnego obiektu o dowolnym przeznaczeniu i dowolnych cechach konstrukcyjnych. Jedyny warunek jaki stawia się przed obiektem to możliwość jego opisu strukturą połączeń elementów jednowyjściowych. Konsekwencją stanie się wtedy możliwość poznania m.in. jego: warstw, silnych spójności, zamknięć tranzytywnych i zamknięć antytranzytywnych. Typowymi narzędziami tego poznania są macierze: przejść i osiągalności. Powodem wybrania pompy wirowej jest nie tylko jej ważkość i powszechność użycia, ale i specyfika współdziałania jej elementów. Można wśród nich wyróżnić: niezależność, zależność i współzależność. Poszczególnym rozróżnialnym stanom diagnostycznym wyznaczono prawdopodobieństwa ich wystąpienia. Owe prawdopodobieństwa stały się przyczynkiem do kalkulacji entropii struktury i intensywności przejść od stanu zdatności do poszczególnych stanów niezdatności. Wyniki kalkulacji zobrazowano stosownymi wykresami. Odniesiono się do metod bayesowskich i nierozłącznej z nimi „szeregowej struktury niezawodnościowej” wykazując ich wady, spowodowane zwłaszcza uproszczeniami prowadzącymi do fałszywych i niejednoznacznych diagnoz. Prawdopodobieństwa zdatności poszczególnych elementów zróżnicowano doborem adekwatnym im wykładników Weibulla.

18

Chapman-Kolmogorov Equations for a Complete Set of Distinct Reliability States of an Object

51%

Szczepański P. , Żurek J.

|

2018

|

tom Vol. 9, Nr 4 (34)

49--70

EN

The Chapman-Kolmogorov equations indicated in the title are a pretext to demonstrate a mathematically unrecognised truth about the effect of the reliability states of elements (which are generally understood as “subjects”) on the reliability states of a complete set of the same elements, which is called an object. Of importance here are not just the reliability characteristics of individual elements, but the independencies, dependencies and interdependencies between the elements. The relations were described in the language of graph theory. The availability matrix of the language of graph theory was translated to determine the size and probabilities of distinct reliability states of the object, the derivatives of their similarities, and the transition rates adequate to those derivatives. This article continues the research work which identifies the relationship of the properties of a complete set of distinct reliability states of an object with a widely understood theory of systems. The previous papers referred, among others, to: risk, safety, structure entropy, the reliability of the results of checks, and – most of all – technical diagnostics, both in the area of its algorithms and of its optimisation. The object’s serial reliability structure was not assumed in any of those papers, recognising that it would be a serious abuse. The research results were referred to all possible structures of a three-element object. It is believed that by virtue of the block diagrams appropriate to those structures, the readers hereof are provided with a realistic opportunity to practically (and inexpensively) verify the ideas presented here.

PL

W artykule tytułowe „równania Chapmana-Kołmogorowa” są pretekstem do ukazania nieuświadomionej matematycznie prawdy o wpływie stanów diagnostycznych elementów (szeroko pojętych podmiotów) na stany diagnostyczne całego swojego zbioru, nazywanego krótko obiektem. Istotne są tu nie tylko charakterystyki niezawodnościowe poszczególnych elementów, ale przede wszystkim występujące między tymi elementami relacje niezależności, zależności i współzależności. Do opisu tych relacji posłużono się językiem teorii grafów, którego macierz osiągalności przełożono dla potrzeb wyznaczania: liczebności i prawdopodobieństw rozróżnialnych stanów diagnostycznych obiektu, pochodnych rzeczonych prawdopodobieństw i adekwatnych tym pochodnym – intensywności przejść. Niniejszy artykuł jest kontynuacją prac wskazujących na związek właściwości pełnego zbioru rozróżnialnych stanów diagnostycznych obiektu z szeroko pojętą teorią systemów. Wcześniejsze prace odnosiły się m.in. do: ryzyka, bezpieczeństwa, entropii struktury, wiarygodności wyników sprawdzeń i – przede wszystkim – diagnostyki technicznej, tak w obszarze jej algorytmów, jak i optymalizacji. W żadnej z nich nie założono szeregowej struktury niezawodnościowej obiektu. Przykłady analiz odniesiono do wszystkich możliwych struktur konstrukcyjnych obiektu trzyelementowego. Żywi się przekonanie, że wraz z podaniem przystających do tych struktur schematów ideowych stwarza się Czytelnikowi realną możliwość praktycznej (i taniej) weryfikacji przedstawionych przemyśleń.

19

Digraph-building method for finding a set of minimal realizations of 2-D dynamic systems

51%

Markowski K. A. , Hryniów K.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2018

|

tom Vol. 66, nr 5

589--597

EN

This paper presents a digraph-building method designed to find the determination of realization of two-dimensional dynamic system. The main differences between the method proposed and other state-of-the-art solutions used include finding a set of realizations (belonging to a defined class) instead of only one realization, and the fact that obtained realizations have minimal size of state matrices. In the article, the proposed method is described, compared to state-of-the-art methods and illustrated with numerical examples. To the best of authors’ knowledge, the method shown in the paper is superior to all other state-of-the-art solutions both in terms of number of solutions and their matrix size. Additionally, MATLAB function for determination of realization based on the set of state matrices is included.

20

Český zápis problematických pádů polských proprií s jednofunkčním písmenem i v koncové slabice

41%

Beneš M.

Naše řeč (Our Speech)

|

2015

|

tom 98

|

nr 3

129-138

EN

The paper deals with the spelling of cases of Polish proper names in Czech, the written nominative ending of which is preceded by the digraph ending in the so-called mono-functional letter i (conf. e.g. Świnoujś-ci-e, Bogaty-ni-a, Ka-si-a). It describes the essence of the problem, gathers all the relevant types of Polish proper names for consideration, enumerates cases in which Czech spelling could be (at least potentially) objectively problematic, presents possible arguments for possible Czech spellings and discusses them, and, finally, recommends one of them for general use.