Graphs with three mutually pseudo-similar vertices

Vertices u and v of a graph X are pseudo-similar if X ? u ? X ? v but no automorphism of X maps u to v. We describe a group-theoretic method for constructing graphs with a set of three mutually pseudo-similar vertices. The method is used to construct several examples of such graphs. An algorithm for extending, in a natural way, certain graphs with three mutually pseudo-similar vertices to a graph in which the three vertices are similar is given. The algorithm suggests that no simple characterization of graphs with a set of three mutually pseudo-similar vertices can exist.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

On pseudosimilarity in trees

Two vertices u and v in a graph G are said to be removal-similar if G\u ? G\v. Vertices which are removal-similar but not similar are said to be pseudosimilar. A characterization theorem is presented for trees (later extended to forests and block graphs) with pseudosimilar vertices. It follows from this characterization that it is not possible to have three or more mutually pseudosimilar vertices in trees. Furthermore, removal-similarity combined with an extension of removal-similarity to include the removal of first neighbourhoods of vertices is sufficient to imply similarity in trees. Neither of these results holds, in general, if we replace trees by arbitrary graphs.     

Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

Hamiltonicity of 3-Arc Graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.     

Geodesic-pancyclic graphs

A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by d_G(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is panconnected if, for each pair of vertices u,v∈V(G) and for each integer k with d_G(u,v)?k?n-1, there is a path of length k in G that connects u and v. A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices u,v∈V(G), every u-v geodesic lies on every cycle of length k satisfying max{2d_G(u,v),3}?k?n. In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs.     

Domination critical graphs

A set of vertices S is said to dominate the graph G if for each v ? S, there is a vertex u ∈ S with u adjacent to v. The smallest cardinality of any such dominating set is called the domination number of G and is denoted by γ(G). The purpose of this paper is to initiate an investigation of those graphs which are critical in the following sense: For each v, u ∈ V(G) with v not adjacent to u, γ(G + vu) < γ(G). Thus G is k-y-critical if γ(G) = k and for each edge e ? E(G), γ(G + e) = k ?1. The 2-domination critical graphs are characterized the properties of the k-critical graphs with k ≥ 3 are studied. In particular, the connected 3-critical graphs of even order are shown to have a 1-factor and some stringent restrictions on their degree sequences and diameters are obtained.     

The strong metric dimension of graphs and digraphs

Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied.     

Graphs with a Minimal Number of Convex Sets

Let G be a graph with vertex set V(G). A set C of vertices of G is g-convex if for every pair \({u, v \in C}\) the vertices on every u–v geodesic (i.e. shortest u–v path) belong to C. If the only g-convex sets of G are the empty set, V(G), all singletons and all edges, then G is called a g-minimal graph. It is shown that a graph is g-minimal if and only if it is triangle-free and if it has the property that the convex hull of every pair of non-adjacent vertices is V(G). Several properties of g-minimal graphs are established and it is shown that every triangle-free graph is an induced subgraph of a g-minimal graph. Recursive constructions of g-minimal graphs are described and bounds for the number of edges in these graphs are given. It is shown that the roots of the generating polynomials of the number of g-convex sets of each size of a g-minimal graphs are bounded, in contrast to their behaviour over all graphs. A set C of vertices of a graph is m-convex if for every pair \({u, v \in C}\) , the vertices of every induced u–v path belong to C. A graph is m-minimal if it has no m-convex sets other than the empty set, the singletons, the edges and the entire vertex set. Sharp bounds on the number of edges in these graphs are given and graphs that are m-minimal are shown to be precisely the 2-connected, triangle-free graphs for which no pair of adjacent vertices forms a vertex cut-set.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

A study of 3-arc graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v,u,x,y) of vertices such that both (v,u,x) and (u,x,y) are paths of length two. The 3-arc graph of a graph G is defined to have the arcs of G as vertices such that two arcs uv,xy are adjacent if and only if (v,u,x,y) is a 3-arc of G. In this paper, we study the independence, domination and chromatic numbers of 3-arc graphs and obtain sharp lower and upper bounds for them. We introduce a new notion of arc-coloring of a graph in studying vertex-colorings of 3-arc graphs.     

Results on the edge-connectivity of graphs

It is shown that if G is a graph of order p ≥ 2 such that deg u + deg v ≥ p ? 1 for all pairs u, v of nonadjacent vertices, then the edge-connectivity of G equals the minimum degree of G. Furthermore, if deg u + deg v ≥ p for all pairs u, v of nonadjacent vertices, then either p is even and G is isomorphic to $\text{K}{}_{\mathrm{<mtext>p</mtext><mtext>2</mtext>}}\text{× K}{}_2$ or every minimum cutset of edges of G consists of the collection of edges incident with a vertex of least degree.     

The eavesdropping number of a graph

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.     

Triangle path transit functions, betweenness and pseudo-modular graphs

The geodesic and induced path transit functions are the two well-studied interval functions in graphs. Two important transit functions related to the geodesic and induced path functions are the triangle path transit functions which consist of all vertices on all u,v-shortest (induced) paths or all vertices adjacent to two adjacent vertices on all u,v-shortest (induced) paths, for any two vertices u and v in a connected graph G. In this paper we study the two triangle path transit functions, namely the I^Δ and J^Δ on G. We discuss the betweenness axioms, for both triangle path transit functions. Also we present a characterization of pseudo-modular graphs using the transit function I^Δ by forbidden subgraphs.     

Diameter and connectivity of 3-arc graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v,u,x,y) of vertices such that both (v,u,x) and (u,x,y) are paths of length two. The 3-arc graph of a given graph G, X(G), is defined to have vertices the arcs of G. Two arcs uv,xy are adjacent in X(G) if and only if (v,u,x,y) is a 3-arc of G. This notion was introduced in recent studies of arc-transitive graphs. In this paper we study diameter and connectivity of 3-arc graphs. In particular, we obtain sharp bounds for the diameter and connectivity of X(G) in terms of the corresponding invariant of G.     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).     

Graph parameters measuring neighbourhoods in graphs—Bounds and applications

The neighbourhood-width of a graph G=(V,E) is introduced in [F. Gurski, Linear layouts measuring neighbourhoods in graphs, Discrete Math. 306 (15) (2006) 1637-1650.] as the smallest integer k such that there is a linear layout ?:V→{1,…,|V|} such that for every 1?i<|V| the vertices u with ?(u)?i can be divided into at most k subsets each members having the same neighbours with respect to the vertices v with ?(v)>i.In this paper we show first bounds for the neighbourhood-width of general graphs, caterpillars, trees and grid graphs and give applications of the layout parameter neighbourhood-width in graph drawing and VLSI design.     

On spanning connected graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if the set of the vertices of all the paths in C(u,v) contains all the vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k^*-connected graphs.     

On a conjecture of the Randi? index

The Randi? index of a graph G is defined as , where d(u) is the degree of vertex u and the summation goes over all pairs of adjacent vertices u, v. A conjecture on R(G) for connected graph G is as follows: R(G)≥r(G)−1, where r(G) denotes the radius of G. We proved that the conjecture is true for biregular graphs, connected graphs with order n≤10 and tricyclic graphs.     

Constructing and classifying neighborhood anti-Sperner graphs

For a simple graph G let N_G(u) be the (open) neighborhood of vertex u∈V(G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a v∈V(G)?{u} with N_G(u)⊆N_G(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_H(u)≠N_H(v) when u≠v, for all u and v∈V(H).In Porter and Yucas [T.D. Porter, J.L. Yucas. Graphs whose vertex-neighborhoods are anti-sperner, Bulletin of the Institute of Combinatorics and its Applications 44 (2005) 69-77] a characterization of regular NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to all NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected r-regular NAS graphs for r=0,1,…,6.