Wyniki wyszukiwania - BazTech

1

On edge product cordial graphs

Ivanco Jaroslav

Opuscula Mathematica

|

2019

|

Vol. 39, no. 5

691--703

EN

An edge product cordial labeling is a variant of the well-known cordial labeling. In this paper we characterize graphs admitting an edge product cordial labeling. Using this characterization we investigate the edge product cordiality of broad classes of graphs, namely, dense graphs, dense bipartite graphs, connected regular graphs, unions of some graphs, direct products of some bipartite graphs, joins of some graphs, maximal k-degenerate and related graphs, product cordial graphs.

2

Signed star (k, k)-domatic number of a graph

Sheikholeslami S. M., Volkmann L.

Opuscula Mathematica

|

2014

|

Vol. 34, no. 3

609--620

EN

Let G be a simple graph without isolated vertices with vertex set V (G) and edge set E(G) and let k be a positive integer. A function ƒ: E(G) →{−1, 1} is said to be a signed star k-dominating function on [formula] for every vertex v of G, where E(v) = {uv ∈ E(G) | u ∈ N(v)}. A set {f1, f2, . . . , fd} of signed star k-dominating functions on G with the property that [formula] for each e ∈ E(G) is called a signed star (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed star (k, k)-dominating family on G is the signed star (k, k)-domatic number of G, denoted by [formula]. In this paper we study properties of the signed star (k, k)-domatic number [formula]. In particular, we present bounds on [formula], and we determine the signed (k, k)-domatic number of some regular graphs. Some of our results extend these given by Atapour, Sheikholeslami, Ghameslou and Volkmann [Signed star domatic number of a graph, Discrete Appl. Math. 158 (2010), 213–218] for the signed star domatic number.

3

Deciding Whether or Not a Synchronous Relation is Regular Prefix

Choffrut C.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 4

439--459

EN

Eilenberg and al. introduced and studied in the late sixties the family of n-ary relations over the free monoid recognized by finite n-tape automata where the where the n reading heads tapes move simultaneously from left to right. We call these relations synchronous. In the eighties Angluin and Hoover and then L¨auchli and Savioz introduced a proper subfamily which the first authors called regular prefix. Our main result shows that given a synchronous relation it is decidable whether or not it is regular prefix. Incidentallywe also show that the family of regular prefix relations is uniformizable in the sense that all such relations contain a partial function with the same domain whose graph is a regular prefix relation.

4

Signed star {k}-domatic number of a graph

Atapour M., Sheikholeslami S. M., Volkmann L.

Fasciculi Mathematici

|

2013

|

Nr 51

33--43

EN

Let G be a simple graph without isolated vertices with vertex set V(G) and edge set E(G) and let k be a positive integer. A function f : E(G) —> {±1, ±2,..., ±k} is said to be a signed star {k}-dominating function on G if Σe∈E(v) ≥ k for every vertex v of G, where E(v) = {uv ∈ E(G) | u ∈ N(v)}. The signed star {k}-domination number of a graph G is y{k}ss(G) = min{ Σe∈Ef(v) | f is a SS{k}DF on G}. A set {f1, f2,..., fd} of distinct signed star {k}-dominating functions on G with the property that …[wzór] for each e ∈ E(G), is called a signed star {k}-dominating family (of functions) on G. The maximum number of functions in a signed star {k}-dominating family on G is the signed star {k}-domatic number of G, denoted by d{k}SS(G). In this paper we study the properties of the signed star {k}- domination number y{k}SS(G) and signed star {k}-domatic number d{k}SS(G). In particular, we determine the signed star {k}-domination number of some classes of graphs. Some of our results extend these one given by Xu [7] for the signed star domination number and Atapour et al. [1] for the signed star domatic number.

5

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs

Karpinski M., Kowaluk M., Lingas A.

Fundamenta Informaticae

|

2004

|

Vol. 62, nr 3,4

369--375

EN

The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 ≤ k Ł≤8, by deriving some improved transformations from a maximum cut into a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively.

6

Grafy regularne w projektowaniu wielokanałowych optycznych systemów komunikacji

Hajder M., Mazurek M.

Zeszyty Naukowe Politechniki Rzeszowskiej. Informatyka

|

2003

|

z. 1 [203]

5-20

PL

W pracy zaprezentowano metodę projektowania topologii logicznych optycznych systemów komunikacji. W pierwszej kolejności autorzy uzasadniają potrzebę szerokiego wykorzystania wielokanałowych systemów optycznych. Następnie zaprezentowano topologie optycznych systemów komunikacyjnych oraz metody ich budowy. W drugiej części pracy zaproponowano metodę budowy topologii logicznych opartą na zastosowaniu skalowanych grafów regularnych. Jako przykłady grafów tej klasy omówiono grafy: nieparzyste, de Bruijna. Moebiusa, Kautza. Dla wybranych topologii zaprezentowano algorytmy marszrutyzacji (trasowania). Przedstawiona metoda charakteryzuje się ograniczoną złożonością obliczeniową i quasi-optymalnością procesu projektowania.

EN

This paper presents logical topology designing method for optical communications systems. First authors motivate necessity wide use of multichannel optical systems. Next authors present topology of optical systems and method for their designing. In the second part authors propose logical topology designing method, which use regular graphs. As example authors present few regular graphs: odd-graphs. de Bruijn, Moebius, Kautz. For some topologies authors shows routing algorithms. Presented method is: computing low-complexity and quasi optimal designing process.

7

Heuristic Approaches to the Maximization of the Number of Spanning Trees in Regular Graphs

Sawionek B., Wojciechowski J., Arabas J.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2000

|

Vol. 48, nr 4

573-586

EN

The paper deals with a fundamental problem arising in the design of optimal network structures - maximization of the number of spanning trees. To make the problem computationally tractable, we consider a class of regular graphs. The problem is solved with the usage of evolutionary and 2-opt algorithms. The problem-specific genetic operators are introduced. Various experiments with different graphs structures have been performed, the results are reported, and the methods compared. Influence of introducing some preliminary knowledge about the problem on the algorithm effectiveness is studied.