A locally irregular graph is a graph in which the end vertices of every edge have distinct degrees. A locally irregular edge coloring of a graph G is any edge coloring of G such that each of the ...colors induces a locally irregular subgraph of G. A graph G is colorable if it allows a locally irregular edge coloring. The locally irregular chromatic index of a colorable graph G, denoted by χirr′(G), is the smallest number of colors used by a locally irregular edge coloring of G. The local irregularity conjecture claims that all graphs, except odd-length paths, odd-length cycles and a certain class of cacti are colorable by three colors. As the conjecture is valid for graphs with a large minimum degree and all non-colorable graphs are vertex disjoint cacti, we study rather sparse graphs. In this paper, we give a cactus graph B which contradicts this conjecture, i.e., χirr′(B)=4. Nevertheless, we show that the conjecture holds for unicyclic graphs and cacti with vertex disjoint cycles.
The classical (vertex) metric dimension of a graph
G
is defined as the cardinality of a smallest set
S
⊆
V
(
G
)
such that any two vertices
x
and
y
from
G
have different distances to least one vertex ...from
S
. The
k
-metric dimension is a generalization of that notion where it is required that any pair of vertices has different distances to at least
k
vertices from
S
. In this paper, we introduce the weak
k
-metric dimension of a graph
G
, which is defined as the cardinality of a smallest set of vertices
S
such that the sum of the distance differences from any pair of vertices to all vertices of
S
is at least
k
. This dimension is “stronger” than the classical metric dimension, yet “weaker” than
k
-metric dimension, and it can be formulated as an ILP problem. The maximum
k
for which the weak
k
-metric dimension is defined is denoted by
κ
(
G
)
.
We first prove several properties of the weak
k
-metric dimension regarding the presence of true or false twin vertices in a graph. Using those properties, the
κ
(
G
)
is found for some basic graph classes, such as paths, stars, cycles, and complete (bipartite) graphs. We also find
κ
(
G
)
for trees and grid graphs using the observation that the distance difference increases by the increase of the cardinality of a set
S
. For all these graph classes we further establish the exact value of the weak
k
-metric dimension for all
k
≤
κ
(
G
)
.
Complex construction projects are developed in a dynamic environment, where uncertainty conditions have a great potential to affect project deliverables. In an attempt to efficiently deal with the ...negative impacts of uncertainty, resilient baseline schedules are produced to improve the probability of reaching project goals, such as respecting the due date and reaching the expected profit. Prior to introducing the resilient scheduling procedure, a taxonomy model was built to account for uncertainty sources in construction projects. Thence, a multi-objective optimization model is presented to manage the impact of uncertainty. This approach can be described as a complex trade-off analysis between three important features of a construction project: duration, stability, and profit. The result of the suggested procedure is presented in a form of a resilient baseline schedule, so the ability of a schedule to absorb uncertain perturbations is improved. The proposed optimization problem is illustrated on the example project network, along which the probabilistic simulation method was used to validate the results of the scheduling process in uncertain conditions. The proposed resilient scheduling approach leads to more accurate forecasting, so the project planning calculations are accepted with increased confidence levels.
The vertex (respectively edge) metric dimension of a graph G is the size of a smallest vertex set in G, which distinguishes all pairs of vertices (respectively edges) in G, and it is denoted by ...dim(G) (respectively edim(G)). The upper bounds dim(G)≤2c(G)−1 and edim(G)≤2c(G)−1, where c(G) denotes the cyclomatic number of G, were established to hold for cacti without leaves distinct from cycles, and moreover, all leafless cacti that attain the bounds were characterized. It was further conjectured that the same bounds hold for general connected graphs without leaves, and this conjecture was supported by showing that the problem reduces to 2-connected graphs. In this paper, we focus on Θ-graphs, as the most simple 2-connected graphs distinct from the cycle, and show that the the upper bound 2c(G)−1 holds for both metric dimensions of Θ-graphs; we characterize all Θ-graphs for which the bound is attained. We conclude by conjecturing that there are no other extremal graphs for the bound 2c(G)−1 in the class of leafless graphs besides already known extremal cacti and extremal Θ-graphs mentioned here.
During the execution of construction projects, uncertain events, such as delays, prolongations and disruptions of project activities, have the potential to cause a significant deviation between the ...planned and realized state of a project. As a result, progress on important project objectives can decrease and this leads to critical delays as well as heavy profit loss. For this reason, we propose the implementation of the customized evolutionary algorithm to generate resilient baseline schedules which include a sufficient number of time floats to absorb the negative impact of uncertainty. This way, the baseline solution is searched as a trade-off between project duration, its final profit and the overall baseline stability. The proposed algorithm is applied to real construction project data and the results of the analysis suggest improved stability for resilient baseline schedules. Application of the genetic algorithm to solve the existing multi-objective problem enables practical implementation of new technologies and methods in construction management. Resilient baseline schedules can be used in an uncertain environment to achieve more accurate predictions and support decision making in the areas of construction scheduling and costing.
•In the second revision of the paper we have corrected the paper according to the suggestions of the reviewer. This includes slight revision of two proofs according to remarks 2. and 6. of the ...reviewer, while other remarks are mainly mistypes which are accordingly corrected. We thank the reviewer for the careful reading of the paper.
In a graph G, cardinality of the smallest ordered set of vertices that distinguishes every element of V(G) is the (vertex) metric dimension of G. Similarly, the cardinality of such a set is the edge metric dimension of G, if it distinguishes E(G). In this paper these invariants are considered first for unicyclic graphs, and it is shown that the vertex and edge metric dimensions obtain values from two particular consecutive integers, which can be determined from the structure of the graph. In particular, as a consequence, we obtain that these two invariants can differ by at most one for a same unicyclic graph. Next we extend the results to graphs with edge disjoint cycles (i.e. cactus graphs) showing that the two invariants can differ by at most c, where c is the number of cycles in such a graph. We conclude the paper with a conjecture that generalizes the previously mentioned consequences to graphs with prescribed cyclomatic number c by claiming that the difference of the invariant is still bounded by c.
•Prove that for unbalanced Θ-graphs the strict inequality holds.•Prove that for balanced Θ-graphs the equality is attained.•Further conjecture that balanced Θ-graphs, besides trees and cactus graph ...in which every cycle has precisely one vertex of degree ≥ 3 for which it was already known that equality holds, are the only graphs for which this upper bound is attained.
In a graph G, the cardinality of the smallest ordered set of vertices that distinguishes every element of V(G)∪E(G) is called the mixed metric dimension of G, and it is denoted by mdim(G). In 12 it was conjectured that every graph G with cyclomatic number c(G) satisfies mdim(G)≤L1(G)+2c(G) where L1(G) is the number of leaves in G. It is already proven that the equality holds for all trees and more generally for graphs with edge-disjoint cycles in which every cycle has precisely one vertex of degree ≥3. In this paper we determine that for every Θ-graph G, the mixed metric dimension mdim(G) equals 3 or 4, with 4 being attained if and only if G is a balanced Θ-graph. Thus, for balanced Θ-graphs the above inequality is also tight. We conclude the paper by further conjecturing that there are no other graphs, besides the ones mentioned here, for which the equality mdim(G)=L1(G)+2c(G) holds.
•We prove that the upper bound L(G)+2c(G) for the vertex and the edge metric dimensions of cacti cannot be attained of a cactus graph has no leaves.•Since in a leafless cacti it holds that L(G)=0, ...the first next bound is 2c(G)−1, and for this bound we prove that there exist leafless cacti which attain it and we characterize all of them.•We further conjecture that the decreased upper bound 2c(G)−1 holds for the vertex and the edge metric dimension all graphs without leaves.•We support this conjecture by showing that it holds for all graphs with minimum degree at least three and that it is sufficient to show that it holds for all 2-connected graphs.
The vertex (resp. edge) metric dimension of a connected graph G, denoted by dim(G) (resp. edim(G)), is defined as the size of a smallest set S⊆V(G) which distinguishes all pairs of vertices (resp. edges) in G. Bounds dim(G)≤L(G)+2c(G) and edim(G)≤L(G)+2c(G), where c(G) is the cyclomatic number in G and L(G) depends on the number of leaves in G, are known to hold for cacti and it is conjectured that they hold for general graphs. In leafless graphs it holds that L(G)=0, so for such graphs the conjectured upper bound becomes 2c(G). In this paper, we show that the bound 2c(G) cannot be attained by leafless cacti, so the upper bound for such cacti decreases to 2c(G)−1, and we characterize all extremal leafless cacti for the decreased bound. We conjecture that the decreased bound holds for all leafless graphs, i.e. graphs with minimum degree at least two. We support this conjecture by showing that it holds for all graphs with minimum degree at least three and that it is sufficient to show that it holds for all 2-connected graphs, and we also verify the conjecture for graphs of small order.
PDF
