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.
•The gp-number is determined for the Cartesian product of a tree and a complete graph.•The gp-numbers are demonstrated for the Cartesian product of a complete graph with a cycle and that of a ...complete multipartite graph with a path, respectively.•An upper bound on the gp-number is proved for the Cartesian products of any two connected graphs G and H, and the bound is sharp if G and H have diameters at most 2. Moreover, the equality holds if and only if G and H are both generalized complete graphs.
A vertex subset R of a graph G is called a general position set if any triple V0⊆R is non-geodesic, this is, the three elements of V0 do not lie on the same geodesic in G. The general position number (gp-number for short) gp(G) of G is the number of vertices in a largest general position set in G. In this paper we first determine some formulae for the gp-numbers of Cartesian products involving a complete graph and of the Cartesian product of a complete multipartite graph with a path, respectively. Moreover, it is proved that gp(G□H)≤n(G)+n(H)−2 for any Cartesian product G□H with equality holding if and only if G and H are both generalized complete graphs, that is, a special class of graphs with diameters at most 2. Finally several open problems are proposed on the gp-numbers of Cartesian products.
A vertex subset S of a graph G is a general position set of G if no vertex of S lies on a geodesic between two other vertices of S. The cardinality of a largest general position set of G is the ...general position number gp(G) of G. It is proved that S⊆V(G) is in general position if and only if the components of GS are complete subgraphs, the vertices of which form an in-transitive, distance-constant partition of S. If diam(G)=2, then gp(G) is the maximum of ω(G) and the maximum order of an induced complete multipartite subgraph of the complement of G. As a consequence, gp(G) of a cograph G can be determined in polynomial time. If G is bipartite, then gp(G) ≤ α(G) with equality if diam(G) ∈ {2, 3}. A formula for the general position number of the complement of an arbitrary bipartite graph is deduced and simplified for the complements of trees, of grids, and of hypercubes.
On monophonic position sets in graphs Thomas, Elias John; Chandran S.V., Ullas; Tuite, James ...
Discrete Applied Mathematics,
09/2024, Letnik:
354
Journal Article
Recenzirano
Odprti dostop
The general position problem in graph theory asks for the largest set S of vertices of a graph G such that no shortest path of G contains more than two vertices of S. In this paper we consider a ...variant of the general position problem called the monophonic position problem, obtained by replacing ‘shortest path’ by ‘induced path’. We prove some basic properties and bounds for the monophonic position number of a graph and determine the monophonic position number of some graph families, including unicyclic graphs, complements of bipartite graphs and split graphs. We show that the monophonic position number of triangle-free graphs is bounded above by the independence number. We present realisation results for the general position number, monophonic position number and monophonic hull number. Finally we discuss the complexity of the monophonic position problem.
A set of edges
X
⊆
E
(
G
)
of a graph
G
is an edge general position set if no three edges from
X
lie on a common shortest path. The edge general position number
gp
e
(
G
)
of
G
is the cardinality of ...a largest edge general position set in
G
. Graphs
G
with
gp
e
(
G
)
=
|
E
(
G
)
|
-
1
and with
gp
e
(
G
)
=
3
are respectively characterized. Sharp upper and lower bounds on
gp
e
(
G
)
are proved for block graphs
G
and exact values are determined for several specific block graphs.
The general position problem for graphs was inspired by the no-three-in-line problem from discrete geometry. A set S of vertices of a graph G is a general position set if no shortest path in G ...contains three or more vertices of S. The general position number of G is the number of vertices in a largest general position set. In this paper we investigate the general position numbers of the Mycielskian of graphs. We give tight upper and lower bounds on the general position number of the Mycielskian of a graph G and investigate the structure of the graphs meeting these bounds. We determine this number exactly for common classes of graphs, including cubic graphs and a wide range of trees.
A set of edges
X
⊆
E
(
G
)
of a graph
G
is an edge general position set if no three edges from
X
lie on a common shortest path in
G
. The cardinality of a largest edge general position set of
G
is ...the edge general position number of
G
. In this paper, edge general position sets are investigated in partial cubes. In particular, it is proved that the union of two largest
Θ
-classes of a Fibonacci cube or a Lucas cube is a maximal edge general position set.
A vertex subset
of a graph
is a general position set of
if no vertex of
lies on a geodesic between two other vertices of
. The cardinality of a largest general position set of
is the general position ...number (gp-number) gp(
) of
. The gp-number is determined for some families of Kneser graphs, in particular for
2),
≥ 4, and
3),
≥ 9. A sharp lower bound on the gp-number is proved for Cartesian products of graphs. The gp-number is also determined for joins of graphs, coronas over graphs, and line graphs of complete graphs.
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.
PDF
