A
k
-
rainbow dominating function
(kRDF) of
G
is a function
f
:
V
(
G
)
→
P
(
{
1
,
2
,
…
,
k
}
)
for which
f
(
v
)
=
∅
we have
⋃
u
∈
N
(
v
)
f
(
u
)
=
{
1
,
2
,
…
,
k
}
. The
weight
w
(
f
) of a ...function
f
is defined as
w
(
f
)
=
∑
v
∈
V
(
G
)
f
(
v
)
. The minimum weight of a kRDF of
G
is called the
k-rainbow domination number
of
G
, which is denoted by
γ
rk
(
G
)
. In this paper, we determine the exact values of the 2-rainbow domination numbers of
C
4
□
C
n
and
C
8
□
C
n
. It follows that
γ
r
2
≠
2
γ
for graphs
C
4
□
C
n
(
n
≥
4
) and
C
8
□
C
n
(
n
≥
8
), answering in part a question raised by Brešar.
The mixed fault diameter D(p,q)(G) is the maximum diameter among all subgraphs obtained from graph G by deleting p vertices and q edges. A graph is (p,q)+connected if it remains connected after the ...removal of any p vertices and any q edges. Let F be a (p,q)+connected graph and B≠K2 be a connected graph. Upper bounds for the mixed fault diameter of the Cartesian graph bundle G with fibre F are given. We prove that if q>0, then D(p+1,q)(G)≤D(p,q)(F)+D(B), where D(B) denotes the diameter of B. If q=0 and p>0, then D(p+1,0)(G)≤max{D(p,0)(F),D(p−1,1)(F)}+D(B). In the case when p=q=0, the fault diameter is determined exactly.
Broadcasting on cactus graphs Čevnik, Maja; Žerovnik, Janez
Journal of combinatorial optimization,
2017/1, Letnik:
33, Številka:
1
Journal Article
Recenzirano
Broadcasting is the process of dissemination of a message from one vertex (called originator) to all other vertices in the graph. This task is accomplished by placing a sequence of calls between ...neighboring vertices, where one call requires one unit of time and each call involves exactly two vertices. Each vertex can participate in one call per one unit of time. Determination of the broadcast time of a vertex
x
in arbitrary graph
G
is NP-complete. Problem can be solved in polynomial time for trees and some subclasses of cactus graphs. In this paper broadcasting in cactus graphs is studied. An algorithm that determines broadcast time of any originator with time complexity
O
(
n
) in
k
-restricted cactus graph (where
k
is constant) is given. Furthermore, another algorithm which calculates broadcast time for all vertices in
k
-restricted cactus graph within the same time complexity is outlined. The algorithm also provides an optimal broadcast scheme for every vertex. As a byproduct, broadcast center of a
k
-restricted cactus graph is computed.
Mixed fault diameter of a graph G, D(a,b)(G), is the maximal diameter of G after deletion of any a vertices and any b edges. Special cases are the (vertex) fault diameter DaV=D(a,0) and the edge ...fault diameter DaE=D(0,a). Let G be a Cartesian graph bundle with fibre F over the base graph B. We show that
(1) Da+b+1V(G)≤DaV(F)+DbV(B) when the graphs F and B are kF-connected and kB-connected, 0<a<kF, 0<b<kB, and provided that D(a−1,1)(F)≤DaV(F) and D(b−1,1)(B)≤DbV(B) and
(2) Da+b+1E(G)≤DaE(F)+DbE(B) when the graphs F and B are kF-edge connected and kB-edge connected, 0≤a<kF, 0≤b<kB, and provided that DaE(F)≥2 and DbE(B)≥2.
Perfect codes in direct graph bundles Hrastnik Ladinek, Irena; Žerovnik, Janez
Information processing letters,
09/2015, Letnik:
115, Številka:
9
Journal Article
Recenzirano
•We study existence of perfect codes in direct graph bundles of cycles over cycles.•We start with shifts and proceed with reflections.•A complete characterization of perfect codes in direct graph ...bundles of cycles over cycles is given.
A complete characterization of perfect codes in direct graph bundles of cycles over cycles is given.
The topology of Arnold–Liouville level sets of the real forms of the complex generic Neumann system depends indirectly on the positions of the roots of the special polynomial US(λ). For certain ...polynomials, the existence and positions of the real roots, according to the suitable parameters of the system, is not obvious.
In the paper, a method for checking the existence and positions of the real roots of the polynomials US(λ) is given. The method and algorithm are based on searching of a positive solution of a system of linear equations. In case n=2, we provide a complete solution to the problem of existence of real roots for all special polynomials and determine the topology of the Arnold–Liouville level sets.
Graph Theory
In the frequency allocation problem, we are given a cellular telephone network whose geographical coverage area is divided into cells, where phone calls are serviced by assigned ...frequencies, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e. minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph, where each vertex knows its position in the graph. We present a 1-local 33/24-competitive distributed algorithm for multicoloring a hexagonal graph, thereby improving the previous 1-local 7/5-competitive algorithm.
Let γ ( D ) denote the domination number of a digraph D and let C m □ C n denote the Cartesian product of C m and C n , the directed cycles of length n ≥ m ≥ 3 . Liu et al. obtained the exact values ...of γ ( C m □ C n ) for m up to 6 Domination number of Cartesian products of directed cycles, Inform. Process. Lett. 111 (2010) 36–39. Shao et al. determined the exact values of γ ( C m □ C n ) for m = 6 , 7 On the domination number of Cartesian product of two directed cycles, Journal of Applied Mathematics, Volume 2013, Article ID 619695. Mollard obtained the exact values of γ ( C m □ C n ) for m = 3 k + 2 M. Mollard, On domination of Cartesian product of directed cycles: Results for certain equivalence classes of lengths, Discuss. Math. Graph Theory 33(2) (2013) 387–394.. In this paper, we extend the current known results on C m □ C n with m up to 21. Moreover, the exact values of γ ( C n □ C n ) with n up to 31 are determined.
PDF
