A connected graph G is distance hereditary if every induced path in G is a shortest path. The Interval functionIG(u,v) of a connected graph G is defined as the set of all vertices that lie on some ...shortest u,v-path in G. In this paper, we consider certain types of first-order betweenness axioms framed on an arbitrary function known as transit function and used to characterize the interval function IG of a distance hereditary graph. As a byproduct, we give a new characterization of distance hereditary graphs using these betweenness axioms.
We give a polynomial-time algorithm that, with input a graph G and two vertices u,v of G, decides whether there is an induced uv-path that is longer than the shortest uv-path.
This study demonstrates a hyper‐level control of metal‐ion migration through vacancy‐induced‐percolation (VIP) path to maximize the steep‐slope performance of the threshold selector with excellent ...selectivity and endurance. Highly efficient control over metal‐ion migration through VIP is achieved with sophisticated stack engineering through the material evolution process and refined electrical operation. A thorough analysis of the energetics of metal‐ion‐ and vacancy‐based hybrid filament is performed using density functional theory calculations, which leads to a proper tuning of the biasing scheme. Command over bias‐induced ion migration to control the atomic‐scale filament is the key to maximize the threshold switching (TS) performance. The devices are designed with different diffusive materials and alloys. Precise atomic‐level control is realized with optimized device structure and alloy electrode, which indicates that the TS is safe within the vicinity of quantum contact. Owing to the synergistic impact of localized metal‐ion injection through VIP, alloy electrode material, and atomic‐level filament, the devices exhibit meticulous control of a highly stable TS with a high steep‐slope of <2 mV dec−1, extremely high selectivity of >4 × 1010 with an exceptional endurance >109 cycles, and device yield of 100%, which suggest the applicability of these devices in 1S1R and 1T1R platforms.
The impacts of materials and their migration through vacancies are thoroughly evaluated to control and design a highly stable steep‐slope threshold‐switching device with an extreme selectivity of >4 × 1010 and extreme endurance of >109 by proper tuning of metal‐ion movement through vacancy‐induced path formation.
The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with ...no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication).
Given an undirected graph G=(V,E), the longest induced path problem (LIPP) consists of obtaining a maximum cardinality subset W⊆V such that W induces a simple path in G. In this paper, we propose two ...new formulations with an exponential number of constraints for the problem, together with effective branch-and-cut procedures for its solution. While the first formulation (cec) is based on constraints that explicitly eliminate cycles, the second one (cut) ensures connectivity via cutset constraints. We compare, both theoretically and experimentally, the newly proposed approaches with a state-of-the-art formulation recently proposed in the literature. More specifically, we show that the polyhedra defined by formulation cut and that of the formulation available in the literature are the same. Besides, we show that these two formulations are stronger in theory than cec. We also propose a new branch-and-cut procedure using the new formulations. Computational experiments show that the newly proposed formulation cec, although less strong from a theoretical point of view, is the best performing approach as it can solve all but one of the 1065 benchmark instances used in the literature within the given time limit. In addition, our newly proposed approaches outperform the state-of-the-art formulation when it comes to the median times to solve the instances to optimality. Furthermore, we perform extended computational experiments considering more challenging and hard-to-solve larger instances and evaluate the impacts on the results when offering initial feasible solutions (warm starts) to the formulations.
•Two new formulations and branch-and-cut procedures are proposed.•A theoretical comparison of the formulations is performed.•The strengths of clique inequalities based on vertices and edges are compared.•The new formulations computationally outperform those available in the literature.•A new benchmark set composed of larger and more challenging instances is proposed.
The largest hole in sparse random graphs Draganić, Nemanja; Glock, Stefan; Krivelevich, Michael
Random structures & algorithms,
December 2022, Volume:
61, Issue:
4
Journal Article
Peer reviewed
Open access
We show that for any d=d(n) with d0(ϵ)≤d=o(n), with high probability, the size of a largest induced cycle in the random graph G(n,d/n) is (2±ϵ)ndlogd. This settles a long‐standing open problem in ...random graph theory.
•The longest induced path problem is a challenging optimization problem.•We describe three different linear integer programming models.•We develop an exact iterative algorithm that exploits these ...models.•We describe a simple randomized heuristic.•Computational experiments with real and synthetic data are presented.
The graph diameter, which is defined as the length of the longest shortest path in a graph, is often used to quantify graph communication properties. In particular, the graph diameter provides an intuitive measure of the worst-case pairwise distance. However, in many practical settings, where vertices can either fail or be overloaded or can be destroyed by an adversary and thus cannot be used in any communication or transportation path, it is natural to consider other possible measures of the worst-case distance. One such measure is the longest induced path. The longest induced path problem is defined as the problem of finding a subset of vertices of the largest cardinality such that the induced subgraph is a simple path. In contrast to the polynomially computable graph diameter, this problem is NP-hard. In this paper, we focus on exact solution approaches for the problem based on linear integer programming (IP) techniques. We first propose three conceptually different linear IP models and study their basic properties. To improve the performance of the standard IP solvers, we propose an exact iterative algorithm that solves a sequence of smaller IPs to obtain an optimal solution for the original problem. In addition, we develop a heuristic capable of finding induced paths in large networks. Finally, we conduct an extensive computational study to evaluate the performance of the proposed solution methods.
Given a graph G=(V,E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem ...that every properly coloured graph contains a colourful path on χ(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on χ(G) vertices and prove its correctness when the girth of G is at least χ(G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if χ(G)≥f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G.
Shifting paths to avoidable ones Gurvich, Vladimir; Krnc, Matjaž; Milanič, Martin ...
Journal of graph theory,
20/May , Volume:
100, Issue:
1
Journal Article
Peer reviewed
Open access
An extension of an induced path
P in a graph
G is an induced path
P
′ such that deleting the endpoints of
P
′ results in
P. An induced path in a graph is said to be avoidable if each of its ...extensions is contained in an induced cycle. In 2019, Beisegel, Chudovsky, Gurvich, Milanič, and Servatius conjectured that every graph that contains an induced
k‐vertex path also contains an avoidable induced path of the same length, and proved the result for
k
=
2. The case
k
=
1 was known much earlier, due to a work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all
k in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut. In the present paper, using a similar approach, we strengthen their result from a reconfiguration point of view. Namely, we show that in every graph, each induced path can be transformed to an avoidable one by a sequence of shifts, where two induced
k‐vertex paths are shifts of each other if their union is an induced path with
k
+
1 vertices. We also obtain analogous results for not necessarily induced paths and for walks. In contrast, the statement cannot be extended to trails or to isometric paths.
PDF
