A GENERAL POSITION PROBLEM IN GRAPH THEORY MANUEL, PAUL; KLAVŽAR, SANDI
Bulletin of the Australian Mathematical Society,
10/2018, Letnik:
98, Številka:
2
Journal Article
Recenzirano
The paper introduces a graph theory variation of the general position problem: given a graph
$G$
, determine a largest set
$S$
of vertices of
$G$
such that no three vertices of
$S$
lie on a common ...geodesic. Such a set is a max-gp-set of
$G$
and its size is the gp-number
$\text{gp}(G)$
of
$G$
. Upper bounds on
$\text{gp}(G)$
in terms of different isometric covers are given and used to determine the gp-number of several classes of graphs. Connections between general position sets and packings are investigated and used to give lower bounds on the gp-number. It is also proved that the general position problem is NP-complete.
Protein structures evolved through a complex interplay of cooperative interactions, and it is still very challenging to design new protein folds de novo. Here we present a strategy to design ...self-assembling polypeptide nanostructured polyhedra based on modularization using orthogonal dimerizing segments. We designed and experimentally demonstrated the formation of the tetrahedron that self-assembles from a single polypeptide chain comprising 12 concatenated coiled coil-forming segments separated by flexible peptide hinges. The path of the polypeptide chain is guided by a defined order of segments that traverse each of the six edges of the tetrahedron exactly twice, forming coiled-coil dimers with their corresponding partners. The coincidence of the polypeptide termini in the same vertex is demonstrated by reconstituting a split fluorescent protein in the polypeptide with the correct tetrahedral topology. Polypeptides with a deleted or scrambled segment order fail to self-assemble correctly. This design platform provides a foundation for constructing new topological polypeptide folds based on the set of orthogonal interacting polypeptide segments.
The general position number of a connected graph is the cardinality of a largest set of vertices such that no three pairwise-distinct vertices from the set lie on a common shortest path. In this ...paper it is proved that the general position number is additive on the Cartesian product of two trees.
TRAVERSING A GRAPH IN GENERAL POSITION KLAVŽAR, SANDI; KRISHNAKUMAR, ADITI; TUITE, JAMES ...
Bulletin of the Australian Mathematical Society,
12/2023, Letnik:
108, Številka:
3
Journal Article
Recenzirano
Odprti dostop
Let G be a graph. Assume that to each vertex of a set of vertices
$S\subseteq V(G)$
a robot is assigned. At each stage one robot can move to a neighbouring vertex. Then S is a mobile general position ...set of G if there exists a sequence of moves of the robots such that all the vertices of G are visited while maintaining the general position property at all times. The mobile general position number of G is the cardinality of a largest mobile general position set of G. We give bounds on the mobile general position number and determine exact values for certain common classes of graphs, including block graphs, rooted products, unicyclic graphs, Kneser graphs
$K(n,2)$
and line graphs of complete graphs.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
7.
THE DOMINATION GAME ON SPLIT GRAPHS JAMES, TIJO; KLAVŽAR, SANDI; VIJAYAKUMAR, AMBAT
Bulletin of the Australian Mathematical Society,
04/2019, Letnik:
99, Številka:
2
Journal Article
Recenzirano
We investigate the domination game and the game domination number
$\unicodeSTIX{x1D6FE}_{g}$
in the class of split graphs. We prove that
$\unicodeSTIX{x1D6FE}_{g}(G)\leq n/2$
for any isolate-free
$n$
...-vertex split graph
$G$
, thus strengthening the conjectured
$3n/5$
general bound and supporting Rall’s
$\lceil n/2\rceil$
-conjecture. We also characterise split graphs of even order with
$\unicodeSTIX{x1D6FE}_{g}(G)=n/2$
.
Abstract
The
$\chi $
-stability index
$\mathrm {es}_{\chi }(G)$
of a graph
G
is the minimum number of its edges whose removal results in a graph with chromatic number smaller than that of
G
. We ...consider three open problems from Akbari
et al.
‘Nordhaus–Gaddum and other bounds for the chromatic edge-stability number’,
European J. Combin.
84
(2020), Article no. 103042. We show by examples that a known characterisation of
k
-regular (
$k\le 5$
) graphs
G
with
$\mathrm {es}_{\chi }(G) = 1$
does not extend to
$k\ge 6$
, and we characterise graphs
G
with
$\chi (G)=3$
for which
$\mathrm { es}_{\chi }(G)+\mathrm {es}_{\chi }(\overline {G}) = 2$
. We derive necessary conditions on graphs
G
which attain a known upper bound on
$\mathrm { es}_{\chi }(G)$
in terms of the order and the chromatic number of
G
and show that the conditions are sufficient when
$n\equiv 2 \pmod 3$
and
$\chi (G)=3$
.
•Dominated and dominator colorings are graph colorings which are difficult to compute and frequently arise in applications.•This paper dominated and dominator colorings of graphs are studied under ...some graph operations which are in turn suitable tools to approach NP-hard graph problems.•An application of dominated colorings in genetic networks is proposed.
Dominator coloring of a graph is a proper (vertex) coloring with the property that every vertex is either alone in its color class or adjacent to all vertices of at least one color class. A dominated coloring of a graph is a proper coloring such that every color class is dominated with at least one vertex. The dominator chromatic number of corona products and of edge corona products is determined. Sharp lower and upper bounds are given for the dominated chromatic number of edge corona products. The dominator chromatic number of hierarchical products is bounded from above and the dominated chromatic number of hierarchical products with two factors determined. An application of dominated colorings in genetic networks is also proposed.
PDF
