In this paper we describe types of evolutions of networks (modelled as graphs) by analyzing the compositions between Hamiltonian graphs and graph “bugs”. We identify one type of “superbug”: a bug ...structure that can destroy the Hamiltonicity of a graph (and thus render a potentially-optimal delivery network inefficient), and also describe types of graphbug infections and their effects.
For an integer s≥0, a graph G is s-hamiltonian if for any vertex subset S⊆V(G) with |S|≤s, G−S is hamiltonian, and G is s-hamiltonian connected if for any vertex subset S⊆V(G) with |S|≤s, G−S is ...hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Kučzel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjáček and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of s-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for s≥2, a line graph L(G) is s-hamiltonian if and only if L(G) is (s+2)-connected. In this paper we prove the following.
(i) For an integer s≥2, the line graph L(G) of a claw-free graph G is s-hamiltonian if and only if L(G) is (s+2)-connected.
(ii) The line graph L(G) of a claw-free graph G is 1-hamiltonian connected if and only if L(G) is 4-connected.
•New graph theoretic representation of zeolites based on Single Repeating Unit (SRU).•Algorithmic, optimization and hybrid approaches for identifying SRU.•159 existing and 10000+ hypothetical zeolite ...structures found to be Hamiltonian.•SRU identification can be modeled as Traveling Salesman Problem (TSP).•25–50% Reduction in T-nodes using SRU in comparison to unit cell representation.
Display omitted
Zeolites are microporous materials with periodic framework structures. Efficient representation of crystal frameworks is important for the design and discovery of new zeolites. We explore a graph-theoretic representation, namely Single Repeating Unit (SRU), which utilizes fewest tetrahedral atoms (T-nodes) and their connectivity graph to describe a zeolite framework. SRUs use topologically distinctive T-nodes, thereby significantly reducing the description space. We also propose several approaches to identify SRUs of large crystallographic frameworks. In the optimization-based approach, SRU identification is formulated as a special instance of traveling salesman problem (TSP). We analyze SRUs of 159 existing and over 10,000 hypothetical zeolites that are all observed to be Hamiltonian cycle graph networks. Considerable reduction in T-nodes is also possible using SRUs. For example, the large Chabazite framework is represented using only 12 T-nodes in the Hamiltonian graph representation. Additionally, SRUs provide a systematic approach to generate Aluminum substituted frameworks for different Si/Al ratios.
Let A be a nontrivial abelian group. A connected simple graph G = (V, E) is A -antimagic, if there exists an edge labeling f : E(G)→A ∖ {0A} such that the induced vertex labeling f+(v)=∑{u, ...v}∈E(G)f({u, v}) is a one-to-one map. The integer-antimagic spectrum of a graph G is the set IAM (G)={k : G is ℤk-antimagic and k ≥ 2} . In this paper, we determine the integer-antimagic spectra for all Hamiltonian graphs.
Power graphs: A survey Abawajy, Jemal; Kelarev, Andrei; Chowdhury, Morshed
Electronic journal of graph theory and applications,
11/2013, Letnik:
1, Številka:
2
Journal Article
Recenzirano
Odprti dostop
This article gives a survey of all results on the power graphs of groups and semigroups obtained in the literature. Various conjectures due to other authors, questions and open problems are also ...included.
We apply the Euler tour technique to find subtrees of specified weight as follows. Let
k
,
g
,
N
1
,
N
2
∈
N such that
1
≤
k
≤
N
2
,
g
+
h
>
2 and
2
k
−
4
g
−
h
+
3
≤
N
2
≤
2
k
+
g
+
h
−
2, where
h
...≔
2
N
1
−
N
2. Let
T be a tree of
N
1 vertices and let
c
:
V
(
T
)
→
N be vertex weights such that
c
(
T
)
≔
∑
v
∈
V
(
T
)
c
(
v
)
=
N
2 and
c
(
v
)
≤
k for all
v
∈
V
(
T
). We prove that a subtree
S of
T of weight
k
−
g
+
1
≤
c
(
S
)
≤
k exists and can be found in linear time. We apply it to show, among others, the following:
Every planar hamiltonian graph
G
=
(
V
(
G
)
,
E
(
G
)
) with minimum degree
δ
≥
4 has a cycle of length
k for every
k
∈
{
⌊
∣
V
(
G
)
∣
2
⌋
,
…
,
⌈
∣
V
(
G
)
∣
2
⌉
+
3
} with
3
≤
k
≤
∣
V
(
G
)
∣.
Every 3‐connected planar hamiltonian graph
G with
δ
≥
4 and
∣
V
(
G
)
∣
≥
8 even has a cycle of length
∣
V
(
G
)
∣
2
−
1 or
∣
V
(
G
)
∣
2
−
2.Each of these cycles can be found in linear time if a Hamilton cycle of the graph is given. This study was partially motivated by conjectures of Bondy and Malkevitch on cycle spectra of 4‐connected planar graphs.
•New algorithms for finding uniquely hamiltonian cycles.•Transforming stable fixed edge cycles to uniquely hamiltonian cycles.•Strong properties of a minimum counter example to Bondy and Jackson’s ...conjecture.•Verifies Bondy and Jackson’s conjecture for graphs with up to 25 vertices.
Bondy and Jackson conjectured in 1998 that every planar uniquely hamiltonian graph must have a vertex of degree two. In this work we verify computationally Bondy and Jackson’s conjecture for graphs with up to 25 vertices. Using a reduction we search for graphs that contain a stable fixed-edge cycle or equivalently a stable cycle with one vertex of degree two. For generating candidate graphs we use plantri and for checking if they contain a stable fixed-edge cycle we propose three approaches. Two of them are based on integer linear programming (ILP) and the other is a cycle enumeration algorithm. To reduce the search space we prove several properties a minimum planar graph with minimum degree at least three containing a stable fixed-edge cycle must satisfy, the most significant being triangle freeness. Comparing the three algorithms shows that the enumeration is more effective on small graphs while for larger graphs the ILP-based approaches perform better. Finally, we use the enumeration approach together with plantri to check that there does not exist a planar graph with minimum degree at least three which contains a stable fixed-edge cycle with 24 or fewer vertices.
Spectral results on Hamiltonian problem Liu, Muhuo; Lai, Hong-Jian; Das, Kinkar Ch
Discrete mathematics,
June 2019, 2019-06-00, Letnik:
342, Številka:
6
Journal Article
Recenzirano
Odprti dostop
Let α be a non-negative real number, and let Θ(G,α) be the largest eigenvalue of A(G)+αD(G). Specially, Θ(G,0) and Θ(G,1) are called the spectral radius and signless Laplacian spectral radius of G, ...respectively. A graph G is said to be Hamiltonian (traceable) if it contains a Hamiltonian cycle (path), and a graph G is called Hamilton-connected if any two vertices are connected by a Hamiltonian path in G. The number of edges of G is denoted by e(G). Recently, the (signless Laplacian) spectral property of Hamiltonian (traceable, Hamilton-connected) graphs received much attention. In this paper, we shall give a general result for all these existed results. To do this, we first generalize the concept of Hamiltonian, traceable, and Hamilton-connected to s-suitable, and we secondly present a lower bound for e(G) to confirm the existence of s-suitable graphs. Thirdly, when 0≤α≤1, we obtain a lower bound for Θ(G,α) to confirm the existence of s-suitable graphs. Consequently, our results generalize and improve all these existed results in this field, including the main results of Chen et al. (2018), Feng et al. (2017), Füredi et al. (2017), Ge et al. (2016), Li et al. (2016), Nikiforov et al. (2016), Wei et al. (2019) and Yu et al. (2013, 2014).
PDF
