Edge search in graphs with restricted test sets

Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with cardinality at most p. Then what is the minimum number c_p(G) of questions, which are needed in the worst case to find e?We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for c_p(G). For the case that G is the complete graph K_n the problem described above is equivalent to the (2,n) group testing problem with test sets of cardinality at most p. We present sharp upper and lower bounds for the worst case number c_p of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.     

Edge-connectivity and edge-disjoint spanning trees

Given a graph G, for an integer c∈{2,…,|V(G)|}, define λ_c(G)=min{|X|:X⊆E(G),ω(G−X)≥c}. For a graph G and for an integer c=1,2,…,|V(G)|−1, define,

     

A note on balanced bipartitions

A balanced bipartition of a graph G is a bipartition V₁ and V₂ of V(G) such that −1≤|V₁|−|V₂|≤1. Bollobás and Scott conjectured that if G is a graph with m edges and minimum degree at least 2 then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤m/3, where e(V_i) denotes the number of edges of G with both ends in V_i. In this note, we prove this conjecture for graphs with average degree at least 6 or with minimum degree at least 5. Moreover, we show that if G is a graph with m edges and n vertices, and if the maximum degree Δ(G)=o(n) or the minimum degree δ(G)→∞, then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤(1+o(1))m/4, answering a question of Bollobás and Scott in the affirmative. We also provide a sharp lower bound on max{e(V₁,V₂):V₁,V₂ is a balanced bipartition of G}, in terms of size of a maximum matching, where e(V₁,V₂) denotes the number of edges between V₁ and V₂.     

Universal spaces of subdifferentials of sublinear operators ranging in the cone of bounded lower semicontinuous functions

We study Fréchet’s problem of the universal space for the subdifferentials ?P of continuous sublinear operators P: V → BC(X)_～ which are defined on separable Banach spaces V and range in the cone BC(X)_～ of bounded lower semicontinuous functions on a normal topological space X. We prove that the space of linear compact operators L ^c(? ², C(βX)) is universal in the topology of simple convergence. Here ? ² is a separable Hilbert space, and βX is the Stone-?ech compactification of X. We show that the images of subdifferentials are also subdifferentials of sublinear operators.     

Connectivity,genus, and the number of components in vertex-deleted subgraphs

Let c(G) denote the number of components in a graph G. It is shown that if G has genus γ and isk-connected with k ? 3, then c(G ? X) ? (2/(k ? 2))(| X | ? 2 + 2γ), for all X? V(G) with | X | ? k. Some implications of this result for planar graphs (y = 0) and toroidal graphs (y = 1) are considered.     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.     

An NP-Completeness Result of Edge Search in Graphs

Consider the following generalization of the classical sequential group testing problem for two defective items: suppose a graph G contains n vertices two of which are defective and adjacent. Find the defective vertices by testing whether a subset of vertices of cardinality at most p contains at least one defective vertex or not. What is then the minimum number c _p (G) of tests, which are needed in the worst case to find all defective vertices? In Gerzen (Discrete Math 309(20):5932–5942, 2009), this problem was partly solved by deriving lower and sharp upper bounds for c _p (G). In the present paper we show that the computation of c _p (G) is an NP-complete problem. In addition, we establish some results on c _p (G) for random graphs.     

On local convexity of nonlinear mappings between Banach spaces

We find conditions for a smooth nonlinear map f: U → V between open subsets of Hilbert or Banach spaces to be locally convex in the sense that for some c and each positive ? < c the image f(B _?(x)) of each ?-ball B _?(x) ? U is convex. We give a lower bound on c via the second order Lipschitz constant Lip₂(f), the Lipschitz-open constant Lip_o(f) of f, and the 2-convexity number conv₂(X) of the Banach space X.     

Secure domination critical graphs

A secure dominating set X of a graph G is a dominating set with the property that each vertex u∈V_G−X is adjacent to a vertex v∈X such that (X−{v})∪{u} is dominating. The minimum cardinality of such a set is called the secure domination number, denoted by γ_s(G). We are interested in the effect of edge removal on γ_s(G), and characterize γ_s-ER-critical graphs, i.e. graphs for which γ_s(G−e)>γ_s(G) for any edge e of G, bipartite γ_s-ER-critical graphs and γ_s-ER-critical trees.     

Balanced decomposition of a vertex-colored graph

A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V₁∪?∪V_r is called a balanced decomposition if V_i is a balanced set for 1≤i≤r.In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V₁∪?∪V_r with |V_i|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.     

Some formulations for the group steiner tree problem

The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V(G) and a cost c(e) for each edge of G, finding a minimum-cost subtree that connects at least one vertex from each R∈R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

Global solutions of first order linear systems of ordinary differential equations with distributional coefficients

With the help of our distributional product we define four types of new solutions for first order linear systems of ordinary differential equations with distributional coefficients. These solutions are defined within a convenient space of distributions and they are consistent with the classical ones. For example, it is shown that, in a certain sense, all the solutions of X₁′=(1+δ)X₁−X₂, X₂′=(2+δ′)X₁+4X₂+δ″ have the form X₁(t)=c₁(e^2t−2e^3t)−14e^3t−δ(t), X₂(t)=c₁(4e^3t−e^2t−δ(t))+28e^3t−18δ(t)+δ′(t), where c₁ is an arbitrary constant and δ is the Dirac measure concentrated at zero. In the spirit of our preceding papers (which concern ordinary and partial differential equations) and under certain conditions we also prove existence and uniqueness results for the Cauchy problem.     

Spaces of maps into topological group with the Whitney topology

Let X be a locally compact Polish space and G a non-discrete Polish ANR group. By C(X,G), we denote the topological group of all continuous maps endowed with the Whitney (graph) topology and by Cc(X,G) the subgroup consisting of all maps with compact support. It is known that if X is compact and non-discrete then the space C(X,G) is an l₂-manifold. In this article we show that if X is non-compact and not end-discrete then Cc(X,G) is an (R^∞×l₂)-manifold, and moreover the pair (C(X,G),Cc(X,G)) is locally homeomorphic to the pair of the box and the small box powers of l₂.     

Edge degrees and dominating cycles

The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G, if d(e₁)+d(e₂)>|V(G)|-4 for any remote edges e₁,e₂, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ₂(G)>|V(G)|/2, then all longest cycles are dominating.     

Exponent of a finite group with a fixed-point-free four-group of automorphisms

Let e be a positive integer and G a finite group acted on by the four-group V in such a manner that C _G (V) = 1. Suppose that V contains an element v such that the centralizer C _G (v) has exponent e. Then the exponent of G″, the second derived group of G, is bounded in terms of e only.     

Unitary units in modular group algebras of 2-groups

We study the unitary subgroupV _?(F₂ G) in the group algebras F₂ Gof 2-groups of maximal class over the field F₂of two elements. We show that there does not exist a normal complement to Gin V _?(F₂ G) if and only if Gis the dihedral group of order 2ⁿ(n≥ 5) or the semidihedral group of order 2ⁿ(n≥5). We also describe V _?(F₂ G) when the subgroup Ghas order 8 and 16 and in this case there exist a normal complement of Gin V _?(F₂ G).     

On graphs critical with respect to vertex partition numbers

For k?0, ?_k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?_k(G–e)<?_k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.     

Spanning trails containing given edges

A graph G is Eulerian-connected if for any u and v in V(G), G has a spanning (u,v)-trail. A graph G is edge-Eulerian-connected if for any e^′ and e^″ in E(G), G has a spanning (e^′,e^″)-trail. For an integer r?0, a graph is called r-Eulerian-connected if for any X⊆E(G) with |X|?r, and for any , G has a spanning (u,v)-trail T such that X⊆E(T). The r-edge-Eulerian-connectivity of a graph can be defined similarly. Let θ(r) be the minimum value of k such that every k-edge-connected graph is r-Eulerian-connected. Catlin proved that θ(0)=4. We shall show that θ(r)=4 for 0?r?2, and θ(r)=r+1 for r?3. Results on r-edge-Eulerian connectivity are also discussed.     

[r,s,t]-Coloring of K n,n

Let G=(V(G),E(G)) be a simple graph. Given non-negative integers r,s, and t, an [r,s,t]-coloring of G is a mapping c from V(G)∪E(G) to the color set {0,1,…,k?1} such that |c(v _i )?c(v _j )|≥r for every two adjacent vertices v _i ,v _j , |c(e _i )?c(e _j )|≥s for every two adjacent edges e _i ,e _j , and |c(v _i )?c(e _j )|≥t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number χ _r,s,t (G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We determine χ _r,s,t (K _n,n ) in all cases.