Every connected graph is a query graph

Let V be a set of bit strings of length k, i.e., V ? {0, 1}^k. The query graph Q(V) is defined as follows: the vertices of Q(V) are the elements of V, and {ū, v?} is an edge of Q(V) if and only if no other w? ? V agrees with ū in all the positions in which v? does. If V represents the set of keys for a statistical data base in which queries that match only one key are rejected, then the security of the individual data is related to the graph Q(V). Ernst Leiss showed that graphs belonging to any of several classes could be represented as query graphs and asked whether any connected graph could be so represented. We answer his question in the affirmative by making use of a spanning tree with special properties.     

Geodesics for the capacity metric in doubly connected domains

We give the qualitative behavior of geodesics of the capacity metric defined on the annulus and study the variation of its Gaussian curvature. We make explicit the relation between the capacities, the Bergman kernel and the reduced Bergman kernel on doubly connected domains and give some applications.     

Partitioning a graph into monochromatic connected subgraphs

We show that every -edge-colored graph on vertices with minimum degree at least can be partitioned into two monochromatic connected subgraphs, provided is sufficiently large. This minimum degree condition is tight and the result proves a conjecture of Bal and DeBiasio. We also make progress on another conjecture of Bal and DeBiasio on covering graphs with large minimum degree with monochromatic components of distinct colors.     

The entire graph of a bridgeless connected plane graph is hamiltonian

In this paper we show that the entire graph of a bridgeless connected plane graph is hamiltonian, and that the entire graph of a plane block is hamiltonian connected and vertex pancyclic. In addition, we show that in any block G which is not a circuit, given a vertex v of G and a circuit k of G, there is a path p, suspended in G, such that p is a path in k of length at least 1 and G ? E(p) ? V₀(G ? E(p)) is a block which includes v.     

The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p≥2, a set S⊆V(G) is a geodetic set of G if each vertex v∈V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g_c(G). A connected geodetic set of cardinality g_c(G) is called a g_c-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for and determine the same for some special classes of graphs. For positive integers r,d and n≥d+1 with r≤d≤2r, there exists a connected graph G with , and . Also, for any positive integers 2≤a<b≤c, there exists a connected graph G such that g(G)=a, g_c(G)=b and . A subset T of a g_c-set S is called a forcing subset for S if S is the unique g_c-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f_c(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f_c(G), is f_c(G)=min{f_c(S)}, where the minimum is taken over all g_c-sets S in G. It is shown that for every pair a,b of integers with 0≤a≤b−4, there exists a connected graph G such that f_c(G)=a and g_c(G)=b.     

Distance irredundance and connected domination numbers of a graph

Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γ_k(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number ir_k(G). The authors prove that if an ir_k-set X is a k-independent set of G, then , and that for k?2, if ir_k(G)=1, if ir_k(G) is odd, and if ir_k(G) is even, which generalize some known results.     

Every connected regular graph of even degree is a Schreier coset graph

Using Petersen's theorem, that every regular graph of even degree is 2-factorable, it is proved that every connected regular graph of even degree is isomorphic to a Schreier coset graph. The method used is a special application of the permutation voltage graph construction developed by the author and Tucker. This work is related to graph imbedding theory, because a Schreier coset graph is a covering space of a bouquet of circles.     

On the distance function of a connected graph

An axiomatic characterization of the distance function of a connected graph is given in this note. The triangle inequality is not contained in this characterization.     

The w-median of a connected strongly chordal graph

Suppose G = (V, E) is a graph in which every vertex x has a non-negative real number w(x) as its weight. The w-distance sum of a vertex y is D_{G, w}(y) = σ_x?v d(y, x)w(x). The w-median of G is the set of all vertices y with minimum w-distance sum D_G,w(y). This paper shows that the w-median of a connected strongly chordal graph G is a clique when w(x) is positive for all vertices x in G.     

Enumeration of connected graph coverings

The number of the isomorphism classes of n-fold coverings of a graph G is enumerated by the authors (Canad. J. Math. XLII (1990), 747–761) and Hofmeister (Discrete Math. 98 (1991), 175–183). But the enumeration of the isomorphism classes of connected n-fold coverings of a graph has not been studied except for n = 2. In this paper, we enumerate the isomorphism classes of connected n-fold coverings of a graph G for any n. As a consequence, we obtain a formula for finding the total number of conjugacy classes of subgroups of a given index of a finitely generated free group. © 1996 John Wiley & Sons, Inc.     

Reconfiguration of connected graph partitions

Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph $G$ and an integer $k\ge 1$, a $k$-district map of $G$ is a partition of $V\left(G\right)$ into $k$ nonempty subsets, called districts, each of which induces a connected subgraph of $G$. A switch is an operation that modifies a $k$-district map by reassigning a subset of vertices from one district to an adjacent district; a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all $k$-district maps of a graph $G$ under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is PSPACE-complete to decide whether there exists a sequence of 1-switches that takes a given $k$-district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial lengths is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that take a given $k$-district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors.     

Every connected,locally connected graph is upper embeddable

In this Note it is proved that every connected, locally connected graph is upper embeddable. Moreover, a lower bound for the maximum genus of the square of a connected graph is given.     

Bounding the distance among longest paths in a connected graph

It is easy to see that in a connected graph any $2$ longest paths have a vertex in common. For $k\ge 7$, Skupień in 1966 obtained a connected graph in which some $k$ longest paths have no common vertex, but every $k?1$ longest paths have a common vertex. It is not known whether every $3$ longest paths in a connected graph have a common vertex and similarly for 4, 5, and $6$ longest path. Fujita et al. in 2015 give an upper bound on distance among $3$ longest paths in a connected graph. In this paper we give a similar upper bound on distance between $4$ longest paths and also for $k$ longest paths, in general.     

The interval function of a connected graph and road systems

Let V be a finite nonempty set. In this paper, a road system on V (as a generalization of the set of all geodesics in a connected graph G with V(G)=V) and an intervaloid function on V (as a generalization of the interval function (in the sense of Mulder) of a connected graph G with V(G)=V) are introduced. A natural bijection of the set of all intervaloid functions on V onto the set of all road systems on V is constructed. This bijection enables to deduce an axiomatic characterization of the interval function of a connected graph G from a characterization of the set of all geodesics in G.     

Every 4-connected line graph of a quasi claw-free graph is hamiltonian connected

Let G be a graph. For u,vV(G) with dist_G(u,v)=2, denote J_G(u,v)={wN_G(u)∩N_G(v)|N_G(w)N_G(u)N_G(v){u,v}}. A graph G is called quasi claw-free if J_G(u,v)≠ for any u,vV(G) with dist_G(u,v)=2. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. In this paper we show that every 4-connected line graph of a quasi claw-free graph is hamiltonian connected.     

Bounds on the connected domination number of a graph

A subset S$S$ of vertices in a graph G=(V,E)$G=(V,E)$ is a connected dominating set of G$G$ if every vertex of V?S$V?S$ is adjacent to a vertex in S$S$ and the subgraph induced by S$S$ is connected. The minimum cardinality of a connected dominating set of G$G$ is the connected domination number _γc(G)${\gamma }_c\left(G\right)$. The girth g(G)$g\left(G\right)$ is the length of a shortest cycle in G$G$. We show that if G$G$ is a connected graph that contains at least one cycle, then _γc(G)≥g(G)−2${\gamma }_c\left(G\right)\ge g\left(G\right)-2$, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus–Gaddum type results.     

Diameter-sufficient conditions for a graph to be super-restricted connected

A vertex-cut X is said to be a restricted cut of a graph G if it is a vertex-cut such that no vertex u in G has all its neighbors in X. Clearly, each connected component of G−X must have at least two vertices. The restricted connectivity κ^′(G) of a connected graph G is defined as the minimum cardinality of a restricted cut. Additionally, if the deletion of a minimum restricted cut isolates one edge, then the graph is said to be super-restricted connected. In this paper, several sufficient conditions yielding super-restricted-connected graphs are given in terms of the girth and the diameter. The corresponding problem for super-edge-restricted-connected graph is also studied.