Wyniki wyszukiwania - BazTech

1

On the General Position Number of Complementary Prisms

Neethu P. K., Chandran S. V. Ullas, Changat Manoj, Klavžar Sandi

Fundamenta Informaticae

|

2021

|

Vol. 178, nr 3

267--281

EN

The general position number gp(G ) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S. The complementary prism G G ¯ of G is the graph formed from the disjoint union of G and its complement G ¯ by adding the edges of a perfect matching between them. It is proved that gp(G G ¯ ) ≤ n (G ) + 1 if G is connected and gp(G G ¯ ) ≤ n (G ) if G is disconnected. Graphs G for which gp(G G ¯ ) = n (G ) + 1 holds, provided that both G and G ¯ are connected, are characterized. A sharp lower bound on gp(G G ¯ ) is proved. If G is a connected bipartite graph or a split graph then gp(G G ¯ ) ∈ {n (G ), n (G )+1}. Connected bipartite graphs and block graphs for which gp(G G ¯ ) = n (G ) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order.

2

Computing the Edge Irregularity Strength of Bipartite Graphs and Wheel Related Graphs

Ahmad Ali, Asim Muhammad Ahsan, Assiri Basem, Semaničová-Feňovčíková Andrea

Fundamenta Informaticae

|

2020

|

Vol. 174, nr 1

1--13

EN

A vertex labeling φ : V(G) → {1, 2,... , k} is called an edge irregular k-labeling of a graph G if all edges in G have unique weights. The weight of an edge is defined as the sum of the labels of its incident vertices. The minimum k for which the graph G has an edge irregular k-labeling is called the edge irregularity strength of G, denoted by es(G). In this paper we perform a computer based experiment dealing with the edge irregularity strength of complete bipartite graphs. We also present some bounds on this parameter for wheel related graphs.

3

Applications of Bipartite Graphs and their Adjacency Matrices to Covering-based Rough Sets

Wang J., Zhu W.

Fundamenta Informaticae

|

2017

|

Vol. 156, nr 2

237--254

EN

In this paper, bipartite graphs and their adjacency matrices are applied to equivalently represent covering-based rough sets through three sides, which are approximation operators, properties and reducible elements. Firstly, a bipartite graph is constructed through a covering. According to the constructed bipartite graph, two equivalent representations of a pair of covering upper and lower approximation operators are presented. And an algorithm is designed for computing the pair of covering approximation operators from the viewpoint of these equivalent representations. Some properties and reducible elements of covering-based rough sets are also investigated through the constructed bipartite graph. Finally, an adjacency matrix of the constructed bipartite graph is proposed, and reducible elements in the covering are obtained through the proposed adjacency matrix. Moreover, an equivalent representation of the covering upper approximation operator is presented through the proposed adjacency matrix. In a word, these results show two interesting views, which are graphs and matrices, to investigate covering-based rough sets.

4

Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments

Duraj S., Kopeć P., Kubale M., Pikies T.

Decision Making in Manufacturing and Services

|

2017

|

Vol. 11, no. 1-2

53--61

EN

In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.

5

Notes on topological indices of graph and its complement

Madaras T., Mockovciakova M.

Opuscula Mathematica

|

2013

|

Vol. 33, no. 1

107-115

EN

In this note, we derive the lower bound on the sum for Wiener index of bipartite graph and its bipartite complement, as well as the lower and upper bounds on this sum for the Randić index and Zagreb indices. We also discuss the quality of these bounds.

6

Model przydziału zasobów do zadań w przedsiębiorstwie transportowym

Izdebski M., Jacyna M.

Logistyka

|

2012

|

nr 4

PL

W artykule zdefiniowano ogólny problem przydziału, wyjaśniono pojęcie skojarzenia w grafie dwudzielnym a następnie opisano problem przydziału w przedsiębiorstwie transportowym. Wyznaczono model matematyczny przydziału, funkcję optymalizacyjną.

EN

This article defines a general assignment problem and explains definition of a matching in a bipartite graph. This paper describes an assignment problem of tasks to resources in the transport company. This article contains the mathematical allocation model of tasks, function optimization with constrains.

7

Open trails in digraphs

Cichacz S., Gorlich A.

Opuscula Mathematica

|

2011

|

Vol. 31, no. 4

599-604

EN

It has been shown in [S. Cichacz, A. Görlich, Decomposition of complete bipartite graphs into open trails, Preprint MD 022, (2006)] that any bipartite graph Ka,b, is decomposable into open trails of prescribed even lengths. In this article we consider the corresponding question for directed graphs. We show that the complete directed graphs ↔K n and ↔K a,b are arbitrarily decomposable into directed open trails.

8

On the key exchange with new cubical maps based on graphs

Romańczuk U., Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2011

|

Vol. 11, no. 4

11--19

EN

Families of edge transitive algebraic graphs Fn(K), over the commutative ring K were used for the graph based cryptographic algorithms. We introduce a key exchange protocol defined in terms of bipartite graph An(K), n ≥ 2 with point set Pn and line set Ln isomorphic to n-dimensional free module Kn. Graphs A(n, K) are not vertex and edge transitive. There is a well defined projective limit lim A(n, K) = A(K), n → ∞ which is an infinite bipatrtite graph with point set P = lim Pn and line set L = limLn. Let K be a commutative ring contain at least 3 regular elements (not zero divisors). For each pair of (n, d), n ≥ 2, n ≥ 1 and sequence of elements α1, α2, …, α2d, such that α1, αi+αi+1, i = 1, 2, …, 2d, i = 1, 2, … 2d-1 and α2d+α1 are regular elements of the ring K. We define polynomial automorphism hn = hn (d, α1, α2, …, α2d) of variety Ln (or Pn). The existence of projective limit lim An(K) guarantees the existence of projective limit h = h(d, α1, α2, …, α2d) = lim hn, n → ∞ which is cubical automorphism of infinite dimensional varieties L (or P). We state that the order of h is an infinity. There is a constant n0 such that hn, n ≥ n0 is a cubical map. Obviously the order of hn is growing with the growth of n and the degree of polynomial map (hn)k from the Cremona group of all polynomial automorphisms of free module Kn with operation of composition is bounded by 3. Let τ be affine automorphism of Kn i.e. the element of Cremona group of degree 1. We suggest symbolic Diffie Hellman key exchange with the use of cyclic subgroup of Cremona group generated by τ-1hnτ. In the case of K = Fp, p is prime, the order of hn is the power of p. So the order is growing with the growth of p. We use computer simulation to evaluate the orders in some cases of K = Zm, where m is a composite integer.

9

Endomorphism monoid of diamond product of two common complete bipartite graphs

Jiarasuksakun T., Rutjanisarakul T., Thongjua W.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

2010

|

Vol. 15

59--66

EN

An endomorphism of a graph G = (V, E) is a mapping f : V → V such that for all x, y ∈ V if {x, y} ∈ E, then {f (x),f (y)}∈ E. Let End(G) be the class of all endomorphisms of graph G. The diamond product of graph G = (V, E) (denoted by G ◊ G) is a graph defined by the vertex set V (G ◊ G) = End(G) and the edge set E (G ◊ G) ={{f, g} ⊂ End(G)|{f(x), g(x)} ∈ E for all x ∈ V}. Let Km,n be a complete bipartite graph on m + n vertices. This research aims to study the algebraic property of V (Km,n ◊ Km,n) = End(Km,n) after we have found that Km,n ◊ Km,n is also a complete bipartite graph on mmnn + nmmn vertices. The result shows that all of its vertices (endomorphisms) form a noncommutative monoid.

10

Alternatywna metoda rozwiązywania kwadratowego zagadnienia przydziału

Schiff K.

Logistyka

|

2010

|

nr 2

PL

Kwadratowy problem przydziału polega na takim umieszczeniu fabryk (obiektów) w lokalizacjach, aby całkowity koszt wyrażony jako suma iloczynów odległości między obiektami i strumieni towarów przepływających między tymi obiektami był jak najmniejszy. Artykuł ten przedstawia nowy sposób modelowania problemu przy wykorzystaniu grafów dwudzielnych i nowy sposób rozwiązania problemu, krok po kroku, polegający na znalezieniu maksymalnego dopasowania o minimalnej wadze z uwzględnieniem fizycznego umiejscowienia fabryk (obiektów) w lokalizacjach.

EN

A new method for quadratic assignment problem is presented. The problem is modeled by a bipartite graph. Hungarian method is used for finding the solution: the assignment with minimum costs is found, but this solution must take into consideration of real objects localizations.

11

3-biplacement of bipartite graphs

Adamus L., Leśniak E., Orchel B.

Opuscula Mathematica

|

2008

|

Vol. 28, no. 3

223-231

EN

Let G = (L,R;E) be a bipartite graph with color classes L and R and edge set E. A set of two bijections {φ1, φ2}, φ1, φ2 : L ∪ R → L ∪ R, is said to be a 3-biplacement of G if [formula], where φ*/1, φ*/2 are the maps defined on E, induced by φ1, φ2, respectively. We prove that if ‌L‌ = p, ‌R‌ = q, 3 ≤ p ≤ q, then every graph G = (L, R; E) of size at most p has a 3-biplacement.

12

Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów

Kosowski A., Kuszner Ł.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 143

75-81

PL

W artykule podano algorytm rozproszonego, samostabilizującego się kolorowania grafów. Rozważamy spójny system niezależnych, asynchronicznych węzłów, z których każdy posiada tylko i wyłącznie lokalną wiedzę o systemie. Bez względu na stan początkowy system powinien osiągnąć pożądany stan globalny, wykonując w każdym z węzłów algorytm dany w postaci zbioru reguł. Zgodnie z naszą wiedzą przedstawiony algorytm jest pierwszym samostabilizującym algorytmem dokładnego kolorowania grafów dwudzielnych, działającym w wielomianowej liczbie ruchów.

EN

In the paper a distributed self-stabilizing algorithm for graph coloring is given. We consider a connected system of autonomous asynchronous nodes, each of which has only local information about the system. Regardless of the initial state, the system must achieve a desirable global state by executing a set of rules assigned to each node. Our method based on spanning trees is applied to give the first (to our knowledge) self-stabilizing algorithms working in a polynomial number of moves, which color bipartite graphs with exactly two colors.

13

Bipartite embedding of (p, q)-trees

Orchel B.

Opuscula Mathematica

|

2006

|

Vol. 26, no. 1

119-125

EN

A bipartite graph G = (L, R; E) where V(G) = L ∪ R, |L| = p, |R| = q is called a (p, q)-tree if |E(G)| = p + q - 1 and G has no cycles. A bipartite graph G = (L, R; E) is a subgraph of a bipartite graph H = (L'. R'; E') if L ⊆ L', R ⊆ R' and E ⊆ E'. In this paper we present sufficient degree conditions for a bipartite graph to contain a (p, q)-tree.

14

Independent set dominanting sets in bipartite graphs

Zelinka B.

Opuscula Mathematica

|

2005

|

Vol. 25, no. 2

345-349

EN

The paper continues the study of independent set dominating sets in graphs which was started by E. Sampathkumar. A subset D of the vertex set V(G) of a graph G is called a set dominating set (shortly sd-set) in G, if for each set X ikkeq V(G) - D there exists a set Y ikkeq D such that the subgraph of G induced X cup Y is connected. The minimum number of vertices of an sd-set in G is called the set domination number gammas (G) of G. An sd-set D in G such that /D/ = gammas(G) is called a gammas-set in G. In this paper we study sd-sets in bipartite graphs which are simultaneously independent. We apply the theory of hypergraphs.

15

2-biplacement without fixed points of (p, q)-bipartite graphs

Orchel B.

Opuscula Mathematica

|

2005

|

Vol. 25, no. 2

269-274

EN

In this paper we consider 2-biplacement without fixed points of paths and (p, q)--bipartite graphs of small size. We give all (p, q)-bipartite graphs G of size q for which the set S*(G) of all 2-biplacements of G without fixed points is empty.