Search

Let D = ( V , E ) be a strongly connected digraph and let u and v be two vertices in D . The maximum distance md( u , v ) is defined as md( u , v ) = max{ d ( u , v ), d ( v , u )} , where d ( u , v ) denotes the length of a shortest directed u - v path in D . This is a metric. The boundary, contour, eccentricity and periphery sets of a strongly connected digraph D with respect to this metric have been defined. The boundary-type sets of the strong product of two digraphs is investigated in this article.

Given a graph G, a set S ⊆ V ( G ) is Δ-convex if there is no vertex u ∈ V ( G ) ∖ S forming a triangle with two vertices of S. The Δ-convex hull of S is the minimum Δ-convex set containing S. The Δ-hull number of a graph G is the cardinality of a minimum set such that its Δ-convex hull is V ( G ) . We show that the problem of deciding whether the Δ-hull number of a general graph is at most k is an NP -complete problem and present polynomial-time algorithms for computing the Δ-hull number of some graph classes including chordal graphs, dually chordal graphs, and cographs.

A set of vertices S of a graph G is geodesically convex if for every pair of vertices of S, all vertices of all shortest paths joining them also lie in S. The geodetic convex hull of S, denoted by 〈 S 〉 , is the minimum geodesically convex set of G containing S. We say that S is Caratheodory independent if 〈 S 〉 ∖ ( ⋃ a ∈ S 〈 S ∖ { a } 〉 ) ≠ ∅ and that S is exchange independent if | S | = 1 or there is p ∈ S such that 〈 S ∖ { p } 〉 ∖ ⋃ a ∈ S ∖ { p } 〈 S ∖ { a } 〉 ≠ ∅ . The Caratheodory number (exchange number) of G is the cardinality of a maximum Caratheodory (exchange) independent set. In this paper, we show that deciding whether a given graph has exchange number at most k is an NP -complete problem. We also present characterizations of the Caratheodory and exchange numbers for some graph classes, like unit interval graphs and powers of cycles, which allow us to determine these parameters in polynomial time.

The \(\varDelta \)-interval of \(u,v \in V (G)\), \(I_{\varDelta }(u,v)\), is the set formed by u, v and every w in V(G) such that \(\{u, v, w\}\) is a triangle \((K_3)\) of G. A set S of vertices such that \(I_{\varDelta } (S)=V(G)\) is called a \(\varDelta \)-set. \(\varDelta \)-number is the minimum cardinality of a \(\varDelta \)-set. \(\varDelta \)-graph is a graph with all the vertices lie on some triangles. If a block graph is a \(\varDelta \)-graph, then we say that it is a block \(\varDelta \)-graph. A set \(S\subseteq V (G)\) is \(\varDelta \)-convex if there is no vertex \(u \in V(G)\setminus S\) forming a triangle with two vertices of S. The convexity number of a graph G with respect to the \(\varDelta \)-convexity is the maximum cardinality of a proper convex subset of G. We have given an exact value for the convexity number of block \(\varDelta \)-graphs with diameter \({\le }3\), block \(\varDelta \)-graphs with diameter \({>}3\) and the two standard graph products (Strong, Lexicographic products), a bound for Cartesian product. Also discussed some bounds for \(\varDelta \)-number and a realization is done for the \(\varDelta \)-number and the hull number.

For a nontrivial connected graph \(G=(V(G),E(G)),\) a set \(S\subseteq V(G)\) is called an edge geodetic set of G if every edge of G is contained in a geodesic joining some pair of vertices in S. The edge geodetic number eg(G) of G is the minimum order of its edge geodetic sets. It is observed that the edge geodetic sets and numbers are interesting concepts and possess properties distinct from the vertex geodetic concepts. In this work, we determine some bounds and exact values of the edge geodetic numbers of strong and lexicographic products of graphs.

We describe in present work all minimal clique separators of all four standard products: the Cartesian, the strong, the direct, and the lexicographic, as well as all maximal atoms of the Cartesian, the strong and the lexicographic product, while we only partially describe maximal atoms of the direct product. In most cases a product have no clique separator and is thus the hole product the maximal atom.

Geodesic convex sets, Steiner convex sets, and J-convex (alias induced path convex) sets of lexicographic products of graphs are characterized. The geodesic case in particular rectifies Theorem 3.1 in Canoy and Garces (Graphs Combin 18(4):787–793, 2002).

We discuss the convexity invariants, namely, the exchange and Helly numbers of the Steiner and geodesic convexity in lexicographic product of graphs. We use the structure of both the Steiner and geodesic convex sets in the lexicographic product for proving the results. Along the way the exchange number of the induced path convexity in arbitrary graphs is also determined.