Undecidability of Winkler′s r-Neighborhood Problem for Covering Digraphs

Consider the following decision problem which P. Winkler and V. Bulitko (independently) showed was undecidable: Given a finite set Φ of rooted graphs and a positive integer r, is there a graph G such that Φ represents, up to isomorphism, the set of all r-neighborhoods of G? We show the undecidability of the related problem in which G is required to be the covering digraph of a partial ordering. Our construction shows that the problem remains undecidable (for certain fixed r) even when G is also required to be planar and bipartite.     

Transitive partial actions of groups

J. Kellendonk and M. V. Lawson established that each partial action of a group G on a set Y can be extended to a global action of G on a set Y _G containing a copy of Y. In this paper we classify transitive partial group actions. When G is a topological group acting on a topological space Y partially and transitively we give a condition for having a Hausdorff topology on Y _G such that the global group action of G on Y _G is continuous and the injection Y into Y _G is an open dense equivariant embedding.      

Wave Invariants of the Spectrum of the G-Invariant Laplacian and the Basic Spectrum of a Riemannian Foliation

Given a compact boundaryless Riemannian manifold upon which a compact Lie group G acts by isometries, recall that the G-invariant Laplacian is the restriction of the ordinary Laplacian on functions to the space of functions which are constant along the orbits of the action. By considering the wave trace of the invariant Laplacian and the connection between G manifolds and Riemannian foliations, invariants of the spectrum of the G-invariant Laplacian can be computed. These invariants include the lengths of certain geodesic arcs which are orthogonal to the principal orbits and contained in the open dense set of principal orbits are associated to the singularities of the wave trace of the G-invariant spectrum. If the action admits finite orbits, then the invariants also include the lengths of certain geodesics arcs connecting the finite orbit to itself. Under additional hypotheses, we obtain partial wave traces. As an application, a partial trace formula for Riemannian foliations with bundle-like metrics is also presented, as well as several special cases where better results are available.     

Restricted T-universal functions on multiply connected domains

Let G ⊂ C be a domain which is bounded by a finite number of pairwise disjoint Jordan curves. We prove the existence of a function which is holomorphic exactly on G and has universal translates with respect to a prescribed set E ⊂∂G and which in addition is continuous on G ^-\E. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Cohen–Lusk theorem

Let G be a finite group and X be a G-space. For a map f: X → ℝ ^m , the partial coincidence set A(f, k), k ≤ |G|, is the set of points x ∈ X such that there exist k elements g ₁,…, g _k of the group G, for which f(g ₁ x) = ⋅⋅⋅ = f(g _k x) holds. We prove that the partial coincidence set is nonempty for G = ℤ _p ⁿ under some additional assumptions. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 8, pp. 61–67, 2007.     

On σ-equivalence and χ-equivalence of graphs

We define a partial ordering on the set of σ-polynomials as well as a vertex splitting operation on the set of graphs, and introduce the notions of σ-equivalence and σ-uniqueness of graphs. Let σ(G) be the σ-polynomial of a graph G and (OVERBAR)σ(G) = σ(G^c). Let H = (G, v, A, B) be a vertex splitting graph of G. We prove that (OVERBAR)σ(G) ≤ (OVERBAR)σ(H) and the equality holds if and only if every vertex of A is adjacent to every vertex of B. This gives us an effective means to find σ-equivalent and χ-equivalent graphs. A necessary and sufficient condition for a graph to be χ-unique but not σ-unique is also obtained. © 1996 John Wiley & Sons, Inc.     

Maximal 2-Local Geometries for the Symmetric Groups

Abstract

The set 𝒩_max (G, T) consisting of all maximal 2-local subgroups of G = Sym(n) which contain T, a Sylow 2-subgroup of G, is investigated. In addition to determining the structure of the subgroups in 𝒩_max (G, T), the simplicial sets of maximal rank are classified.     

The orders of graphs with prescribed degree sets

The degree set ??^G of a graph G is the set of degrees of the vertices of G. For a finite nonempty set S of positive integers, all positive integers p are determined for which there exists a graph G of order p such that ??^G = S.     

Ordering Starlike Trees by the Totality of Their Spectral Moments

The k-th spectral moment M_k(G) of the adjacency matrix of a graph G represents the number of closed walks of length k in G. We study here the partial order ? of graphs, defined by G ? H if M_k(G) ≤ M_k(H) for all k ≥?0, and are interested in the question when is ? a linear order within a specified set of graphs? Our main result is that ? is a linear order on each set of starlike trees with constant number of vertices. Recall that a connected graph G is a starlike tree if it has a vertex u such that the components of G ? u are paths, called the branches of G. It turns out that the ? ordering of starlike trees with constant number of vertices coincides with the shortlex order of sorted sequence of their branch lengths.

     

On minimum secure dominating sets of graphs

A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X/{v}) ? {u} is again a dominating set of G, in which case v is called a defender. The secure domination number of G is the cardinality of a smallest secure dominating set of G. In this paper, we show that every graph of minimum degree at least 2 possesses a minimum secure dominating set in which all vertices are defenders. We also characterise the classes of graphs that have secure domination numbers 1, 2 and 3.     

The Groups of Symmetric Genus σ ≤ 8

Let G be a finite group. The symmetric genus σ (G) is the minimum genus of any compact Riemann surface on which G acts faithfully as a group of automorphisms. Here we classify the groups of symmetric genus σ, for all values of σ such that 4 ≤ σ ≤ 8. In addition, we obtain some general results about the partial presentations that groups acting on surfaces must have. We show that a group with even genus and no “large order” elements in its Sylow 2-subgroup has restrictions on its Sylow 2-subgroup. As a consequence, we show that if G is a 2-group with positive symmetric genus, then σ(G) is odd. The software package MAGMA was employed to help with the calculations, and the MAGMA library of small groups was essential to the classification.     

On Trees with Double Domination Number Equal to the 2-Outer-Independent Domination Number Plus One

A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.     

Nowhere‐zero 3‐flows in products of graphs

A graph G is an odd‐circuit tree if every block of G is an odd length circuit. It is proved in this paper that the product of every pair of graphs G and H admits a nowhere‐zero 3‐flow unless G is an odd‐circuit tree and H has a bridge. This theorem is a partial result to the Tutte's 3‐flow conjecture and generalizes a result by Imrich and Skrekovski [7] that the product of two bipartite graphs admits a nowhere‐zero 3‐flow. A byproduct of this theorem is that every bridgeless Cayley graph G = Cay(Γ,S) on an abelian group Γ with a minimal generating set S admits a nowhere‐zero 3‐flow except for odd prisms. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

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.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

Connected Domination Stable Graphs Upon Edge Addition

Abstract

A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number.     

Partitioning series-parallel multigraphs into ν *-excluding edge covers

We prove that, for any given vertex ν* in a series-parallel graph G, its edge set can be partitioned into κ = min{κ′(G) + 1, δ(G)} subsets such that each subset covers all the vertices of G possibly except for ν*, where δ(G) is the minimum degree of G and κ′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.