On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

Covering shadows with a smaller volume

For n?2 a construction is given for convex bodies K and L in Rn such that the orthogonal projection Lu onto the subspace u^⊥ contains a translate of Ku for every direction u, while the volumes of K and L satisfy Vn(K)>Vn(L).A more general construction is then given for n-dimensional convex bodies K and L such that each orthogonal projection Lξ onto a k-dimensional subspace ξ contains a translate of Kξ, while the mth intrinsic volumes of K and L satisfy Vm(K)>Vm(L) for all m>k.For each k=1,…,n, we then define the collection Cn,k to be the closure (under the Hausdorff topology) of all Blaschke combinations of suitably defined cylinder sets (prisms).It is subsequently shown that, if L∈Cn,k, and if the orthogonal projection Lξ contains a translate of Kξ for every k-dimensional subspace ξ of Rn, then Vn(K)?Vn(L).The families Cn,k, called k-cylinder bodies of Rn, form a strictly increasing chain

Cn,1⊂Cn,2⊂?⊂Cn,n−1⊂Cn,n,     

Coincidences of projections and linear n-valued maps of tori

We prove that the Nielsen fixed point number N(φ) of an n-valued map φ:X?X of a compact connected triangulated orientable q-manifold without boundary is equal to the Nielsen coincidence number of the projections of the graph of φ, a subset of X×X, to the two factors. For certain q×q integer matrices A, there exist “linear” n-valued maps Φn,A,σ:Tq?Tq of q-tori that generalize the single-valued maps fA:Tq→Tq induced by the linear transformations TA:Rq→Rq defined by TA(v)=Av. By calculating the Nielsen coincidence number of the projections of its graph, we calculate N(Φn,A,σ) for a large class of linear n-valued maps.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

The forcing hull and forcing geodetic numbers of graphs

For every pair of vertices u,v in a graph, a u-v geodesic is a shortest path from u to v. For a graph G, let I_G[u,v] denote the set of all vertices lying on a u-v geodesic. Let S⊆V(G) and I_G[S] denote the union of all I_G[u,v] for all u,v∈S. A subset S⊆V(G) is a convex set of G if I_G[S]=S. A convex hull [S]_G of S is a minimum convex set containing S. A subset S of V(G) is a hull set of G if [S]_G=V(G). The hull number h(G) of a graph G is the minimum cardinality of a hull set in G. A subset S of V(G) is a geodetic set if I_G[S]=V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F⊆V(G) is called a forcing hull (or geodetic) subset of G if there exists a unique minimum hull (or geodetic) set containing F. The cardinality of a minimum forcing hull subset in G is called the forcing hull number f_h(G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number f_g(G) of G. In the paper, we construct some 2-connected graph G with (f_h(G),f_g(G))=(0,0),(1,0), or (0,1), and prove that, for any nonnegative integers a, b, and c with a+b≥2, there exists a 2-connected graph G with (f_h(G),f_g(G),h(G),g(G))=(a,b,a+b+c,a+2b+c) or (a,2a+b,a+b+c,2a+2b+c). These results confirm a conjecture of Chartrand and Zhang proposed in [G. Chartrand, P. Zhang, The forcing hull number of a graph, J. Combin. Math. Combin. Comput. 36 (2001) 81-94].     

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.     

Higher rank numerical ranges and low rank perturbations of quantum channels

For a positive integer k, the rank-k numerical range Λk(A) of an operator A acting on a Hilbert space H of dimension at least k is the set of scalars λ such that PAP=λP for some rank k orthogonal projection P. In this paper, a close connection between low rank perturbation of an operator A and Λk(A) is established. In particular, for 1?r<k it is shown that Λk(A)⊆Λk−r(A+F) for any operator F with rank(F)?r. In quantum computing, this result implies that a quantum channel with a k-dimensional error correcting code under a perturbation of rank at most r will still have a (k−r)-dimensional error correcting code. Moreover, it is shown that if A is normal or if the dimension of A is finite, then Λk(A) can be obtained as the intersection of Λk−r(A+F) for a collection of rank r operators F. Examples are given to show that the result fails if A is a general operator. The closure and the interior of the convex set Λk(A) are completely determined. Analogous results are obtained for Λ_∞(A) defined as the set of scalars λ such that PAP=λP for an infinite rank orthogonal projection P. It is shown that Λ_∞(A) is the intersection of all Λk(A) for k=1,2,…. If A−μI is not compact for all μ∈C, then the closure and the interior of Λ_∞(A) coincide with those of the essential numerical range of A. The situation for the special case when A−μI is compact for some μ∈C is also studied.     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.     

Some new spaces of double sequences

In this study, we define the double sequence spaces BS, BS(t), CSp, CSbp, CSr and BV, and also examine some properties of those sequence spaces. Furthermore, we show that these sequence spaces are complete paranormed or normed spaces under some certain conditions. We determine the α-duals of the spaces BS, BV, CSbp and the β(?)-duals of the spaces CSbp and CSr of double series. Finally, we give the conditions which characterize the class of four-dimensional matrix mappings defined on the spaces CSbp, CSr and CSp of double series.     

Strong commutativity preserving maps in prime rings with involution

Let A be a prime ring of characteristic not 2, with center Z(A) and with involution *. Let S be the set of symmetric elements of A. Suppose that f:S→A is an additive map such that [f(x),f(y)]=[x,y] for all x,y∈S. Then unless A is an order in a 4-dimensional central simple algebra, there exists an additive map μ:S→Z(A) such that f(x)=x+μ(x) for all x∈S or f(x)=-x+μ(x) for all x∈S.     

Some bounds on the p-domination number in trees

Let p be a positive integer and G=(V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times, and S is a p-dependent set of G if the subgraph induced by the vertices of S has maximum degree at most p-1. The minimum cardinality of a p-dominating set a of G is the p-domination number γ_p(G) and the maximum cardinality of a p-dependent set of G is the p-dependence number β_p(G). For every positive integer p?2, we show that for a bipartite graph G, γ_p(G) is bounded above by (|V|+|Y_p|)/2, where Y_p is the set of vertices of G of degree at most p-1, and for every tree T, γ_p(T) is bounded below by β_p-1(T). Moreover, we characterize the trees achieving equality in each bound.     

On double bound graphs and forbidden subposets

For a poset P=(X,≤_P), the double bound graph (DB-graph) of P is the graph DB(P)=(X,E_DB(P)), where xy∈E_DB(P) if and only if x≠y and there exist n,m∈X such that n≤_Px,y≤_Pm. We obtain that for a subposet Q of a poset P,Q is an (n, m)-subposet of P if and only if DB(Q) is an induced subgraph DB(P). Using this result, we show some characterizations of split double bound graphs, threshold double bound graphs and difference double bound graphs in terms of (n, m)-subposets and double canonical posets.     

Greedy F-colorings of graphs

Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N₀ is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v₁)=1 and (2) for each i with 1?i<n, c(v_i+1) is the smallest positive integer p such that F(v_j,v_i+1,|c(v_j)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .     

An improvement of the Nevanlinna-Gundersen theorem

A well-known result of Nevanlinna states that for two nonconstant meromorphic functions f and g on the complex plane C and for four distinct values aj∈C∪{∞}, if νf−aj=νg−aj for all 1?j?4, then g is a Möbius transformation of f. In 1983, Gundersen generalized the result of Nevanlinna to the case where the above condition is replaced by: min{νf−aj,1}=min{νg−aj,1} for j=1,2 and νf−aj=νg−aj for j=3,4. In this paper, we prove that the theorem of Gundersen remains valid to the case where min{νf−aj,1}=min{νg−aj,1} for j=1,2, and min{νf−aj,2}=min{νg−aj,2} for j=3,4. Furthermore, we work on the case where {aj} are small functions.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Reduced limits for nonlinear equations with measures

We consider equations (E) −Δu+g(u)=μ in smooth bounded domains Ω⊂RN, where g is a continuous nondecreasing function and μ is a finite measure in Ω. Given a bounded sequence of measures (μk), assume that for each k?1 there exists a solution uk of (E) with datum μk and zero boundary data. We show that if uk→u# in L¹(Ω), then u# is a solution of (E) relative to some finite measure μ#. We call μ# the reduced limit of (μk). This reduced limit has the remarkable property that it does not depend on the boundary data, but only on (μk) and on g. For power nonlinearities g(t)=|t|^q−1t, ∀t∈R, we show that if (μk) is nonnegative and bounded in W−2,q(Ω), then μ and μ# are absolutely continuous with respect to each other; we then produce an example where μ#≠μ.     

Cross-intersecting families of permutations

For positive integers r and n with r?n, let Pr,n be the family of all sets {(1,y₁),(2,y₂),…,(r,yr)} such that y₁,y₂,…,yr are distinct elements of [n]={1,2,…,n}. Pn,n describes permutations of [n]. For r<n, Pr,n describes permutations of r-element subsets of [n]. Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. For any r, n and k?2, we determine the cases in which the sum of sizes of cross-intersecting sub-families A₁,A₂,…,Ak of Pr,n is a maximum, hence solving a recent conjecture (suggested by the author).     

Disjoint triangles and quadrilaterals in a graph

Let G be a simple graph of order n and s and k be two positive integers. Brandt et al. obtained the following result: If s?k, n?3s+4(k-s) and σ₂(G)?n+s, then G contains k disjoint cycles C₁,…,C_k satisfying |C_i|=3 for 1?i?s and |C_i|?4 for s<i?k. In the above result, the length of C_i is not specified for s<i?k. We get a result specifying the length of C_i for each s<i?k if n?3s+4(k-s)+3.     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).     

Perfect dexagon triple systems with given subsystems

The graph consisting of the six triples (or triangles) {a,b,c}, {c,d,e}, {e,f,a}, {x,a,y}, {x,c,z}, {x,e,w}, where a,b,c,d,e,f,x,y,z and w are distinct, is called a dexagon triple. In this case the six edges {a,c}, {c,e}, {e,a}, {x,a}, {x,c}, and {x,e} form a copy of K₄ and are called the inside edges of the dexagon triple. A dexagon triple system of order v is a pair (X,D), where D is a collection of edge disjoint dexagon triples which partitions the edge set of 3K_v. A dexagon triple system is said to be perfect if the inside copies of K₄ form a block design. In this note, we investigate the existence of a dexagon triple system with a subsystem. We show that the necessary conditions for the existence of a dexagon triple system of order v with a sub-dexagon triple system of order u are also sufficient.