For a digraph
D
=
(
V
(
D
)
,
A
(
D
)
)
, and a set
S
⊆
V
(
D
)
with
r
∈
S
and
|
S
|
≥
2
, an (
S
,
r
)-tree is an out-tree
T
rooted at
r
with
S
⊆
V
(
T
)
. Two (
S
,
r
)-trees
T
1
and
T
2
are said ...to be arc-disjoint if
A
(
T
1
)
∩
A
(
T
2
)
=
∅
. Two arc-disjoint (
S
,
r
)-trees
T
1
and
T
2
are said to be internally disjoint if
V
(
T
1
)
∩
V
(
T
2
)
=
S
. Let
κ
S
,
r
(
D
)
and
λ
S
,
r
(
D
)
be the maximum number of internally disjoint and arc-disjoint (
S
,
r
)-trees in
D
, respectively. The generalized
k
-vertex-strong connectivity of
D
is defined as
κ
k
(
D
)
=
min
{
κ
S
,
r
(
D
)
∣
S
⊆
V
(
D
)
,
|
S
|
=
k
,
r
∈
S
}
.
Similarly, the generalized
k
-arc-strong connectivity of
D
is defined as
λ
k
(
D
)
=
min
{
λ
S
,
r
(
D
)
∣
S
⊆
V
(
D
)
,
|
S
|
=
k
,
r
∈
S
}
.
The generalized
k
-vertex-strong connectivity and generalized
k
-arc-strong connectivity are also called directed tree connectivity which could be seen as a generalization of classical connectivity of digraphs and a natural extension of undirected tree connectivity. A digraph
D
=
(
V
(
D
)
,
A
(
D
)
)
is called minimally generalized
(
k
,
ℓ
)
-vertex (respectively, arc)-strongly connected if
κ
k
(
D
)
≥
ℓ
(respectively,
λ
k
(
D
)
≥
ℓ
) but for any arc
e
∈
A
(
D
)
,
κ
k
(
D
-
e
)
≤
ℓ
-
1
(respectively,
λ
k
(
D
-
e
)
≤
ℓ
-
1
). In this paper, we study the minimally generalized
(
k
,
ℓ
)
-vertex (respectively, arc)-strongly connected digraphs. We compute the minimum and maximum sizes of these digraphs and give characterizations of such digraphs for some pairs of
k
and
ℓ
.
Let
D
=
(
V
,
A
)
be a digraph of order
n
,
S
a subset of
V
of size
k
and
2
≤
k
≤
n
. A strong subgraph
H
of
D
is called an
S
-
strong
subgraph if
S
⊆
V
(
H
)
. A pair of
S
-strong subgraphs
D
1
and
...D
2
are said to be
arc-disjoint
if
A
(
D
1
)
∩
A
(
D
2
)
=
∅
. A pair of arc-disjoint
S
-strong subgraphs
D
1
and
D
2
are said to be
internally disjoint
if
V
(
D
1
)
∩
V
(
D
2
)
=
S
. Let
κ
S
(
D
)
(resp.
λ
S
(
D
)
) be the maximum number of internally disjoint (resp. arc-disjoint)
S
-strong subgraphs in
D
. The
strong subgraph
k
-connectivity
is defined as
κ
k
(
D
)
=
min
{
κ
S
(
D
)
∣
S
⊆
V
,
|
S
|
=
k
}
.
As a natural counterpart of the strong subgraph
k
-connectivity, we introduce the concept of
strong subgraph
k
-arc-connectivity
which is defined as
λ
k
(
D
)
=
min
{
λ
S
(
D
)
∣
S
⊆
V
(
D
)
,
|
S
|
=
k
}
.
A digraph
D
=
(
V
,
A
)
is called
minimally strong subgraph
(
k
,
ℓ
)
-(arc-)connected
if
κ
k
(
D
)
≥
ℓ
(resp.
λ
k
(
D
)
≥
ℓ
) but for any arc
e
∈
A
,
κ
k
(
D
-
e
)
≤
ℓ
-
1
(resp.
λ
k
(
D
-
e
)
≤
ℓ
-
1
). In this paper, we first give complexity results for
λ
k
(
D
)
, then obtain some sharp bounds for the parameters
κ
k
(
D
)
and
λ
k
(
D
)
. Finally, minimally strong subgraph
(
k
,
ℓ
)
-connected digraphs and minimally strong subgraph
(
k
,
ℓ
)
-arc-connected digraphs are studied.
Boesch and Chen (SIAM J Appl Math 34:657–665, 1978) introduced the cut-version of the generalized edge-connectivity, named
k
-edge-connectivity. For any integer
k
with
2
≤
k
≤
n
, the
k
...-edge-connectivity
of a graph
G
, denoted by
λ
k
(
G
)
, is defined as the smallest number of edges whose removal from
G
produces a graph with at least
k
components. In this paper, we first compute some exact values and sharp bounds for
λ
k
(
G
)
in terms of
n
and
k
. We then discuss the relationships between
λ
k
(
G
)
and other generalized connectivities. An algorithm in
O
(
n
2
)
time will be provided such that we can compute a sharp upper bound in terms of the maximum degree. Among our results, we also compute some exact values and sharp bounds for the function
f
(
n
,
k
,
t
) which is defined as the minimum size of a connected graph
G
with order
n
and
λ
k
(
G
)
=
t
.
The concept of
-connectivity
), introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. For an integer
≥ 2, the
-connectivity of a connected graph
with ...order
≥
is the smallest number of vertices whose removal from
produces a graph with at least
components or a graph with fewer than
vertices. In this paper, we get a sharp upper bound for the size of
with
) =
, where 1 ≤
≤
−
and
≥ 3; moreover, the unique extremal graph is given. Based on this result, we get the exact values for the maximum size, denoted by
), of a connected graph
with order
and
) =
. We also compute the exact values and bounds for another parameter
) which is defined as the minimum size of a connected graph
with order
and
) =
, where 1 ≤
≤
−
and
≥ 3.
The generalized k-connectivity κ
(G) of a graph G was introduced by Hager in 1985. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized ...k-edge-connectivity which is defined as λ
(G) = min{λ(S) : S ⊆ V (G) and |S| = k}, where λ(S) denote the maximum number ℓ of pairwise edge-disjoint trees T
, T
, . . . , T
in G such that S ⊆ V (T
) for 1 ≤ i ≤ ℓ. In this paper, we study the generalized edge- connectivity of product graphs and obtain sharp upper bounds for the generalized 3-edge-connectivity of Cartesian product graphs and strong product graphs. Among our results, some special cases are also discussed.
The generalized k-connectivity κ
(G) of a graph G, mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. As a natural counterpart of this concept, ...Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λ
(G) = min{λ
(S) | S ⊆ V (G) and |S| = k}, where λ
(S) denote the maximum number ℓ of pairwise edge-disjoint trees T
, T
, . . . , T
in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper we get a sharp lower bound for the generalized 3-edge-connectivity of the strong product of any two connected graphs.
Necroptosis is a form of necrotic cell death that requires the activity of the death domain-containing kinase RIP1 and its family member RIP3. Necroptosis occurs when RIP1 is deubiquitinated to form ...a complex with RIP3 in cells deficient in the death receptor adapter molecule FADD or caspase-8. Necroptosis may play a role in host defense during viral infection as viruses like vaccinia can induce necroptosis while murine cytomegalovirus encodes a viral inhibitor of necroptosis. To see how general the interplay between viruses and necroptosis is, we surveyed seven different viruses. We found that two of the viruses tested, Sendai virus (SeV) and murine gammaherpesvirus-68 (MHV68), are capable of inducing dramatic necroptosis in the fibrosarcoma L929 cell line. We show that MHV68-induced cell death occurs through the cytosolic STING sensor pathway in a TNF-dependent manner. In contrast, SeV-induced death is mostly independent of TNF. Knockdown of the RNA sensing molecule RIG-I or the RIP1 deubiquitin protein, CYLD, but not STING, rescued cells from SeV-induced necroptosis. Accompanying necroptosis, we also find that wild type but not mutant SeV lacking the viral proteins Y1 and Y2 result in the non-ubiquitinated form of RIP1. Expression of Y1 or Y2 alone can suppress RIP1 ubiquitination but CYLD is dispensable for this process. Instead, we found that Y1 and Y2 can inhibit cIAP1-mediated RIP1 ubiquitination. Interestingly, we also found that SeV infection of B6 RIP3
mice results in increased inflammation in the lung and elevated SeV-specific T cells. Collectively, these data identify viruses and pathways that can trigger necroptosis and highlight the dynamic interplay between pathogen-recognition receptors and cell death induction.
Rainbow connections are natural combinatorial measures that are used in applications to secure the transfer of classified information between agencies in communication networks. Rainbow Connections ...of Graphs covers this new and emerging topic in graph theory and brings together a majority of the results that deal with the concept of rainbow connections, first introduced by Chartrand et al. in 2006. The authors begin with an introduction to rainbow connectedness, rainbow coloring, and rainbow connection number. The work is organized into the following categories, computation of the exact values of the rainbow connection numbers for some special graphs, algorithms and complexity analysis, upper bounds in terms of other graph parameters, rainbow connection for dense and sparse graphs, for some graph classes and graph products, rainbow k-connectivity and k-rainbow index, and, rainbow vertex-connection number. Rainbow Connections of Graphs appeals to researchers and graduate students in the field of graph theory. Conjectures, open problems and questions are given throughout the text with the hope for motivating young graph theorists and graduate students to do further study in this subject.
Let
= (
) be a digraph of order
,
a subset of
of size
and 2 ≤
≤
. A subdigraph
of
is called an
-strong subgraph if
is strong and
⊆
(
). Two
-strong subgraphs
and
are said to be arc-disjoint if
) ∩
) ...= ∅. Let
) be the maximum number of arc-disjoint
-strong digraphs in
. The strong subgraph
- arc-connectivity is defined as
) = min{
) |
⊆
|
| =
}. A digraph
= (
) is called minimally strong subgraph (
)-arc-connected if
) ≥
but for any arc
∈
,
−
) ≤
− 1. Let 𝔊 (
) be the set of all minimally strong subgraph (
)-arc-connected digraphs with order
. We define
) = max{|
)| |
∈𝔊 (
)} and
) = min{|
)| |
∈ 𝔊(
)}.
In this paper, we study the minimally strong subgraph (
)-arc-connected digraphs. We give a characterization of the minimally strong sub-graph (3,
− 2)-arc-connected digraphs, and then give exact values and bounds for the functions
) and
).
Stochastic combinatorial optimization problems are usually defined as planning problems, which involve purchasing and allocating resources in order to meet uncertain needs. For example, network ...designers need to make their best guess about the future needs of the network and purchase capabilities accordingly. Facing uncertain in the future, we either “wait and see” changes, or postpone decisions about resource allocation until the requirements or constraints become realized. Specifically, in the field of stochastic combinatorial optimization, some inputs of the problems are uncertain, but follow known probability distributions. Our goal is to find a strategy that minimizes the expected cost. In this paper, we consider the two-stage finite-scenario stochastic set cover problem and the single sink rent-or-buy problem by presenting primal-dual based approximation algorithms for these two problems with approximation ratio
2
η
and 4.39, respectively, where
η
is the maximum frequency of the element of the ground set in the set cover problem.
PDF
