•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.
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.
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.
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.
On independent position sets in graphs Thomas, Elias John; Chandran S. V., Ullas
Proyecciones (Antofagasta, Chile),
04/2021, Letnik:
40, Številka:
2
Journal Article
Recenzirano
Odprti dostop
An independent set S of vertices in a graph G is an independent position set if no three vertices of S lie on a common geodesic. An independent position set of maximum size is an ip-set of G. The ...cardinality of an ip-set is the independent position number, denoted by ip(G). In this paper, we introduce and study the independent position number of a graph. Certain general properties of these concepts are discussed. Graphs of order n having the independent position number 1 or n − 1 are characterized. Bounds for the independent position number of Cartesian and Lexicographic product graphs are determined and the exact value for Corona product graphs are obtained. Finally, some realization results are proved to show that there is no general relationship between independent position sets and other related graph invariants.
PDF
