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.     

Rectilinearization of semi-algebraic p-adic sets and Denef's rationality of Poincaré series

In [R. Cluckers, Classification of semi-algebraic sets up to semi-algebraic bijection, J. Reine Angew. Math. 540 (2001) 105-114], it is shown that a p-adic semi-algebraic set can be partitioned in such a way that each part is semi-algebraically isomorphic to a Cartesian product where the sets R(k) are very basic subsets of Qp. It is suggested in [R. Cluckers, Classification of semi-algebraic sets up to semi-algebraic bijection, J. Reine Angew. Math. 540 (2001) 105-114] that this result can be adapted to become useful to p-adic integration theory, by controlling the Jacobians of the occurring isomorphisms. In this paper we show that the isomorphisms can be chosen in such a way that the valuations of their Jacobians equal the valuations of products of coordinate functions, hence obtaining a kind of explicit p-adic resolution of singularities for semi-algebraic p-adic functions. We do this by restricting the used isomorphisms to a few specific types of functions, and by controlling the order in which they appear. This leads to an alternative proof of the rationality of the Poincaré series associated to the p-adic points on a variety, as proven by Denef in [J. Denef, The rationality of the Poincaré series associated to the p-adic points on a variety, Invent. Math. 77 (1984) 1-23].     

On the Ramsey Number of Sparse 3-Graphs

We consider a hypergraph generalization of a conjecture of Burr and Erd?s concerning the Ramsey number of graphs with bounded degree. It was shown by Chvátal, Rödl, Trotter, and Szemerédi [The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), no. 3, 239–243] that the Ramsey number R(G) of a graph G of bounded maximum degree is linear in |V(G)|. We derive the analogous result for 3-uniform hypergraphs.     

Embeddings of minimal non-abelian p-groups

By a quasi-permutation matrix we mean a square matrix over the complex field C with non-negative integral trace. For a given finite group G, let p(G) denote the minimal degree of a faithful representation of G by permutation matrices, and let c(G) denote the minimal degree of a faithful representation of G by quasi-permutation matrices. See [4]. It is easy to see that c(G) is a lower bound for p(G). Behravesh [H. Behravesh, The minimal degree of a faithful quasi-permutation representation of an abelian group, Glasg. Math. J. 39 (1) (1997) 51-57] determined c(G) for every finite abelian group G and also [H. Behravesh, Quasi-permutation representations of p-groups of class 2, J. Lond. Math. Soc. (2) 55 (2) (1997) 251-260] gave the algorithm of c(G) for each finite group G. In this paper, we first improve this algorithm and then determine c(G) and p(G) for an arbitrary minimal non-abelian p-group G.     

Some inequalities involving upper bounds for some matrix operators I

In this paper we consider the problem of finding upper bounds of certain matrix operators such as Hausdorff, Nörlund matrix, weighted mean and summability on sequence spaces l _p(w) and Lorentz sequence spaces d(w, p), which was recently considered in [9] and [10] and similarly to [14] by Josip Pecaric, Ivan Peric and Rajko Roki. Also, this study is an extension of some works by G. Bennett on l _p spaces, see [1] and [2].     

Binding number and minimum degree for the existence of (g,f,n)-critical graphs

Let G be a graph of order p. The binding number of G is defined as $\mbox{bind}(G):=\min\{\frac{|N_{G}(X)|}{|X|}\mid\emptyset\neq X\subseteq V(G)\,\,\mbox{and}\,\,N_{G}(X)\neq V(G)\}$ . Let g(x) and f(x) be two nonnegative integer-valued functions defined on V(G) with g(x)≤f(x) for any x∈V(G). A graph G is said to be (g,f,n)-critical if G?N has a (g,f)-factor for each N?V(G) with |N|=n. If g(x)≡a and f(x)≡b for all x∈V(G), then a (g,f,n)-critical graph is an (a,b,n)-critical graph. In this paper, several sufficient conditions on binding number and minimum degree for graphs to be (a,b,n)-critical or (g,f,n)-critical are given. Moreover, we show that the results in this paper are best possible in some sense.     

Convexity properties of gradient maps

We consider the action of a real reductive group G on a Kähler manifold Z which is the restriction of a holomorphic action of a complex reductive group H. We assume that the action of a maximal compact subgroup U of H is Hamiltonian and that G is compatible with a Cartan decomposition of H. We have an associated gradient map μp:Z→p where g=k⊕p is the Cartan decomposition of g. For a G-stable subset Y of Z we consider convexity properties of the intersection of μp(Y) with a closed Weyl chamber in a maximal abelian subspace a of p. Our main result is a Convexity Theorem for real semi-algebraic subsets Y of Z=P(V) where V is a unitary representation of U.     

Hamilton-connected indices of graphs

Let G be an undirected graph that is neither a path nor a cycle. Clark and Wormald [L.H. Clark, N.C. Wormald, Hamiltonian-like indices of graphs, ARS Combinatoria 15 (1983) 131-148] defined hc(G) to be the least integer m such that the iterated line graph L^m(G) is Hamilton-connected. Let be the diameter of G and k be the length of a longest path whose internal vertices, if any, have degree 2 in G. In this paper, we show that . We also show that κ³(G)≤hc(G)≤κ³(G)+2 where κ³(G) is the least integer m such that L^m(G) is 3-connected. Finally we prove that hc(G)≤|V(G)|−Δ(G)+1. These bounds are all sharp.     

Edge sets contained in circuits

A graphG withn vertices has propertyp(r, s) ifG contains a path of lengthr and if every such path is contained in a circuit of lengths. G. A. Dirac and C. Thomassen [Math. Ann.203 (1973), 65–75] determined graphs with propertyp(r,r+1). We determine the least number of edges in a graphG in order to insure thatG has propertyp(r,s), we determine the least number of edges possible in a connected graph with propertyp(r,s) forr=1 and alls, forr=k ands=k+2 whenk=2, 3, 4, and we give bounds in other cases. Some resulting extremal graphs are determined. We also consider a generalization of propertyp(2,s) in which it is required that each pair of edges is contained in a circuit of lengths. Some cases of this last property have been treated previously by U. S. R. Murty [inProof Techniques in Graph Theory, ed. F. Harary, Academic Press, New York, 1969, pp. 111–118].     

On algebraic connectivity augmentation

Suppose that G is an undirected graph, and that H is a spanning subgraph of G^c whose edges induce a subgraph on p vertices. We consider the expression α(G∪H)-α(G), where α denotes the algebraic connectivity. Specifically, we provide upper and lower bounds on α(G∪H)-α(G) in terms of p, and characterise the corresponding equality cases. We also discuss the density of the expression α(G∪H)-α(G) in the interval [0,p]. A bound on α(G∪H)-α(G) is provided in a special case, and several examples are considered.     

A characterization of the minimalbasis of the torus

D. König asks the interesting question in [7] whether there are facts corresponding to the theorem of Kuratowski which apply to closed orientable or non-orientable surfaces of any genus. Since then this problem has been solved only for the projective plane ([2], [3], [8]). In order to demonstrate that König’s question can be affirmed we shall first prove, that every minimal graph of the minimal basis of all graphs which cannot be embedded into the orientable surface f of genusp has orientable genusp+1 and non-orientable genusq with 1≦q≦2p+2. Then let f be the torus. We shall derive a characterization of all minimal graphs of the minimal basis with the nonorientable genusq=1 which are not embeddable into the torus. There will be two very important graphs signed withX ₈ andX ₇ later. Furthermore 19 graphsG ₁,G ₂, ...,G ₁₉ of the minimal basisM(torus, >₄) will be specified. We shall prove that five of them have non-orientable genusq=1, ten of them have non-orientable genusq=2 and four of them non-orientable genusq=3. Then we shall point out a method of determining graphs of the minimal basisM(torus, >₄) which are embeddable into the projective plane. Using the possibilities of embedding into the projective plane the results of [2] and [3] are necessary. This method will be called saturation method. Using the minimal basisM(projective plane, >₄) of [3] we shall at last develop a method of determining all graphs ofM(torus, >₄) which have non-orientable genusq≧2. Applying this method we shall succeed in characterizing all minimal graphs which are not embeddable into the torus. The importance of the saturation method will be shown by determining another graphG ₂₀≠G ₁,G ₂, ...,G ₁₉ ofM(torus, >₄).     

Upper minus total domination in small-degree regular graphs

A function f:V(G)→{-1,0,1} defined on the vertices of a graph G is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. An MTDF f is minimal if there does not exist an MTDF g:V(G)→{-1,0,1}, f≠g, for which g(v)?f(v) for every v∈V(G). The weight of an MTDF is the sum of its function values over all vertices. The minus total domination number of G is the minimum weight of an MTDF on G, while the upper minus domination number of G is the maximum weight of a minimal MTDF on G. In this paper we present upper bounds on the upper minus total domination number of a cubic graph and a 4-regular graph and characterize the regular graphs attaining these upper bounds.     

Harmonic analysis on the Iwahori–Hecke algebra

These are purely expository notes of Opdam’s analysis [O1] of the trace form τ(f) = f(e) on the Hecke algebra H = C _c (I\G/I) of compactly supported functions f on a connected reductive split p-adic group G which are biinvariant under an Iwahori subgroup I, extending Macdonald’s work. We attempt to give details of the proofs, and choose notations which seem to us more standard. Many objects of harmonic analysis are met: principal series, Macdonald’s spherical forms, trace forms, Bernstein forms. The latter were introduced by Opdam under the name Eisenstein series for H. The idea of the proof is that the last two linear forms are proportional, and the proportionality constant is computed by projection to Macdonald’s spherical forms. Crucial use is made of Bernstein’s presentation of the Iwahori–Hecke algebra by means of generators and relations, as an extension of a finite dimensional algebra by a large commutative subalgebra. We give a complete proof of this using the universal unramified principal series right H-module M = C _c (A(O)N\G/I) to develop a theory of intertwining operators algebraically.     

Long cycles in graphs without hamiltonian paths

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. Bondy and Locke [J.A. Bondy, S.C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122] consider the gap between p(G) and c(G) in 3-connected graphs G. Starting with this result, there are many results appeared in this context, see [H. Enomoto, J. van den Heuvel, A. Kaneko, A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225; M. Lu, H. Liu, F. Tian, Relative length of longest paths and cycles in graphs, Graphs Combin. 23 (2007) 433-443; K. Ozeki, M. Tsugaki, T. Yamashita, On relative length of longest paths and cycles, preprint; I. Schiermeyer, M. Tewes, Longest paths and longest cycles in graphs with large degree sums, Graphs Combin. 18 (2002) 633-643]. In this paper, we investigate graphs G with p(G)−c(G) at most 1 or at most 2, but with no hamiltonian paths. Let G be a 2-connected graph of order n, which has no hamiltonian paths. We show two results as follows: (i) if , then p(G)−c(G)≤1, and (ii) if σ₄(G)≥n+3, then p(G)−c(G)≤2.     

More on “Connected (n, m)-graphs with minimum and maximum zeroth-order general Randi? index”

Let G be a graph and d(u) denote the degree of a vertex u in G. The zeroth-order general Randi? index ⁰R_α(G) of the graph G is defined as ∑_u∈V(G)d(u)^α, where the summation goes over all vertices of G and α is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected (n,m)-graphs with minimum and maximum zeroth-order general Randi? index, Discrete Appl. Math. 155 (8) (2007) 1044-1054] and give a more general Theorem. We finally characterize ¹ for α<0 the connected G(n,m)-graphs with maximum value ⁰R_α(G(n,m)), where G(n,m) is a simple connected graph with n vertices and m edges.     

On diameter and inverse degree of a graph

The inverse degree r(G) of a finite graph G=(V,E) is defined as , where is the degree of vertex v. We establish inequalities concerning the sum of the diameter and the inverse degree of a graph which for the most part are tight. We also find upper bounds on the diameter of a graph in terms of its inverse degree for several important classes of graphs. For these classes, our results improve bounds by Erd?s et al. (1988) [5], and by Dankelmann et al. (2008) [4].     

New Bounds for Perfect Hashing via Information Theory

A set of sequences of length t from a b-element alphabet is called k-separated if for every k-tuple of the sequences there exists a coordinate in which they all differ. The problem of finding, for fixed t, b, and k, the largest size N(t, b, k) of a k-separated set of sequences is equivalent to finding the minimum size of a (b, k)-family of perfect hash functions for a set of a given size. We shall improve the bounds for N(t, b, k) obtained by Fredman and Komlós [1].Körner [2] has shown that the proof in [1] can be reduced to an application of the sub-additivity of graph entropy [3]. He also pointed out that this sub-additivity yields a method to prove non-existence bounds for graph covering problems. Our new non-existence bound is based on an extension of graph entropy to hypergraphs.     

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 the Probabilistic Zeta Function for Finite Groups

LetGbe a finite group, and define the function[formula]where μ is the Möbius function on the subgroup lattice ofG. The functionP(G, s) is the multiplicative inverse of a zeta function forG, as described by Mann and Boston. Boston conjectured thatP′(G, 1) = 0 ifGis a nonabelian simple. We will prove a generalization of this conjecture, showing thatP′(G, 1) = 0 unlessG/O_p(G) is cyclic for some primep.