Connected graphs containing a given connected graph as a unique greatest common subgraph.
On graphs with a unique minimum hull set
We show that for every integer k ≥ 2 and every k graphs G₁,G₂,...,Gₖ, there exists a hull graph with k hull vertices v₁,v₂,...,vₖ such that link for 1 ≤ i ≤ k. Moreover, every pair a, b of integers with 2 ≤ a ≤ b is realizable as the hull number and geodetic number (or upper geodetic number) of a hull graph. We also show that every pair a,b of integers with a ≥ 2 and b ≥ 0 is realizable as the hull number and forcing geodetic number of a hull graph.
The forcing geodetic number of a graph
For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on some u-v geodesic in G. If S is a set of vertices of G, then I(S) is the union of all sets I(u,v) for u, v ∈ S. A set S is a geodetic set if I(S) = V(G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T. The forcing geodetic...
Planar Permutation Graphs
Extreme geodesic graphs
For two vertices and of a graph , the closed interval consists of , , and all vertices lying in some geodesic of , while for , the set is the union of all sets for . A set of vertices of for which is a geodetic set for , and the minimum cardinality of a geodetic set is the geodetic number . A vertex in is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in is its extreme order . A graph is an extreme geodesic...
The existence of 2-factors in squares of graphs
The forcing convexity number of a graph
For two vertices and of a connected graph , the set consists of all those vertices lying on a – geodesic in . For a set of vertices of , the union of all sets for is denoted by . A set is a convex set if . The convexity number of is the maximum cardinality of a proper convex set of . A convex set in with is called a maximum convex set. A subset of a maximum convex set of a connected graph is called a forcing subset for if is the unique maximum convex set...
The forcing dimension of a graph
For an ordered set of vertices and a vertex in a connected graph , the (metric) representation of with respect to is the -vector = (), where represents the distance between the vertices and . The set is a resolving set for if distinct vertices of have distinct representations. A resolving set of minimum cardinality is a basis for and the number of vertices in a basis is its (metric) dimension . For a basis of , a subset of is called a forcing subset of if is...
-convex graphs
For two vertices and in a connected graph , the set consists of all those vertices lying on a geodesic in . For a set of vertices of , the union of all sets for is denoted by . A set is convex if . The convexity number is the maximum cardinality of a proper convex set in . A convex set is maximum if . The cardinality of a maximum convex set in a graph is the convexity number of . For a nontrivial connected graph , a connected graph is an -convex graph if contains...
On Regular Bipartite-Preserving Supergraphs. (Short Communication).
On regular bipartite-preserving supergraphs.
On a Special Class of Hamiltonian Graphs.
On Hamiltonian properties of powers of special Hamiltonian graphs
The coarseness of a graph
Geodetic sets in graphs
For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in some u-v geodesic in G. If S is a set of vertices of G, then I[S] is the union of all sets I[u,v] for u, v ∈ S. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for...
Distance defined by spanning trees in graphs
For a spanning tree T in a nontrivial connected graph G and for vertices u and v in G, there exists a unique u-v path u = u₀, u₁, u₂,..., uₖ = v in T. A u-v T-path in G is a u- v path u = v₀, v₁,...,vₗ = v in G that is a subsequence of the sequence u = u₀, u₁, u₂,..., uₖ = v. A u-v T-path of minimum length is a u-v T-geodesic in G. The T-distance from u to v in G is the length of a u-v T-geodesic. Let geo(G) and geo(G|T) be the set of geodesics and the set of T-geodesics respectively in G. Necessary...
Radio k-colorings of paths
For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of...
On minimal regular digraphs with given girth
Kaleidoscopic Colorings of Graphs
For an r-regular graph G, let c : E(G) → [k] = 1, 2, . . . , k, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if cm(u) ≠ cm(v) for every two distinct vertices u and v of G. A regular graph...
Randomly Eulerian digraphs
Page 1 Next