Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph

The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with x∈V ₁ and y∈V ₂, then, for any k independent edges e ₁,…,e _k of G, G contains k vertex-disjoint quadrilaterals C ₁,…,C _k such that e _i ∈E(C _i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V ₁|=|V ₂|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C ₁,…,C _k containing specified edges of G.     

On 2-factors with cycles containing specified vertices in a bipartite graph

Let k≥1 be an integer and G=(V ₁,V ₂;E) a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+2. Our result is as follows: If $d(x)+d(y)\geq \lceil\frac{4n+k}{3}\rceil$ for any nonadjacent vertices x∈V ₁ and y∈V ₂, then for any k distinct vertices z ₁,…,z _k , G contains a 2-factor with k+1 cycles C ₁,…,C _k+1 such that z _i ∈V(C _i ) and l(C _i )=4 for each i∈{1,…,k}.     

Packing seagulls

A seagull in a graph is an induced three-vertex path. When does a graph G have k pairwise vertex-disjoint seagulls? This is NP-complete in general, but for graphs with no stable set of size three we give a complete solution. This case is of special interest because of a connection with Hadwiger’s conjecture which was the motivation for this research; and we deduce a unification and strengthening of two theorems of Blasiak [2] concerned with Hadwiger’s conjecture. Our main result is that a graph G (different from the five-wheel) with no three-vertex stable set contains k disjoint seagulls if and only if

1. |V (G)|≥3k
2. G is k-connected
3. for every clique C of G, if D denotes the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C then |D|+|V (G)\C|≥2k, and
4. the complement graph of G has a matching with k edges.

We also address the analogous fractional and half-integral packing questions, and give a polynomial time algorithm to test whether there are k disjoint seagulls.     

Odd cycles and matrices with integrality properties

A cycle of a bipartite graphG(V⁺, V^?; E) is odd if its length is 2 (mod 4), even otherwise. An odd cycleC is node minimal if there is no odd cycleC′ of cardinality less than that ofC′ such that one of the following holds:C′ ∩V ⁺ ?C ∩V ⁺ orC′ ∩V ^? ?C ∩V ^?. In this paper we prove the following theorem for bipartite graphs: For a bipartite graphG, one of the following alternatives holds:

-All the cycles ofG are even.

-G has an odd chordless cycle.

-For every node minimal odd cycleC, there exist four nodes inC inducing a cycle of length four.

-An edge (u, v) ofG has the property that the removal ofu, v and their adjacent nodes disconnects the graphG.

To every (0, 1) matrixA we can associate a bipartite graphG(V⁺, V^?; E), whereV ⁺ andV ^? represent respectively the row set and the column set ofA and an edge (i,j) belongs toE if and only ifa _ij = 1. The above theorem, applied to the graphG(V⁺, V^?; E) can be used to show several properties of some classes of balanced and perfect matrices. In particular it implies a decomposition theorem for balanced matrices containing a node minimal odd cycleC, having the property that no four nodes ofC induce a cycle of length 4. The above theorem also yields a proof of the validity of the Strong Perfect Graph Conjecture for graphs that do not containK ₄?e as an induced subgraph.     

Torsion points of elliptic curves over large algebraic extensions of finitely generated fields

The following Theorem is proved:Let K be a finitely generated field over its prime field. Then, for almost all e-tuples (σ)=(σ ₁, …,σ _e)of elements of the abstract Galois group G(K)of K we have:

1. If e=1,then E _tor(K(σ))is infinite. Morover, there exist infinitely many primes l such that E(K(σ))contains points of order l.
2. If e≧2,then E _tor(K(σ))is finite.
3. If e≧1,then for every prime l, the group E(K(σ))contains only finitely many points of an l-power order.

HereK(σ) is the fixed field in the algebraic closureK ofK, ofσ ₁, …,σ _e, and “almost all” is meant in the sense of the Haar measure ofG(K).     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

Pancyclism in Chvátal-Erdös's graphs

LetG = (X, E) be a simple graph of ordern, of stability numberα and of connectivityk withα ≤ k. The Chvátal-Erdös's theorem [3] proves thatG is hamiltonian. We have investigated under these conditions what can be said about the existence of cycles of lengthl. We have obtained several results:

1. IfG ≠ K _k,k andG ≠ C ₅,G has aC _n?1 .
2. IfG ≠ C ₅, the girth ofG is at most four.
3. Ifα = 2 and ifG ≠ C ₄ orC ₅,G is pancyclic.
4. Ifα = 3 and ifG ≠ K _3,3,G has cycles of any length between four andn.
5. IfG has noC ₃,G has aC _n?2 .

     

On the exactness of certain inequalities in approximation theory

We prove the following: for every sequence {F_v}, F_v ? 0, F_v > 0 there exists a functionf such that

1. E_n(f)?F_n (n=0, 1, 2, ...) and
2. A_kn^?k? _v=1 ⁿ v^k?1 F_v?1?Ω_k (f, n^?1) (n=1, 2, ...).

     

Lower bounds on the signed total k-domination number of graphs

Let G be a graph with vertex set V(G). For any integer k ≥ 1, a signed total k-dominating function is a function f: V(G) → {?1, 1} satisfying ∑_x∈N(v)f(x) ≥ k for every v ∈ V(G), where N(v) is the neighborhood of v. The minimum of the values ∑_v∈V(G)f(v), taken over all signed total k-dominating functions f, is called the signed total k-domination number. In this note we present some new sharp lower bounds on the signed total k-domination number of a graph. Some of our results improve known bounds.     

Covering a graph with cycles passing through given edges

We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e₁, …, e_k of G, there exist k vertex-disjoint cycles C₁, …, C_k in G such that e_i ∈ E(C_i) for all i ∈ {1, …, k} and V(C₁ ∪ ···∪ C_k) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

Signed k-independence in graphs

Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ _x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ _v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α _s ^k (G) of G. In this work, we mainly present upper bounds on α _s ^k (G), as for example α _s ^k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.     

Accretion centers: A generalization of branch weight centroids

An ordered n-tuple (v_i1,v_i2,…,v_in) is called a sequential labelling of graph G if {v_i1,v_i2,…,v_in} = V(G) and the subgraph induced by {v_i1,v_i2,…, v_ij} is connected for 1≤j≤n. Let σ(v;G) denote the number of sequential labellings of G with v_i1=v. Vertex v is defined to be an accretion center of G if σ is maximized at v. This is shown to generalize the concept of a branch weight centroid of a tree since a vertex in a tree is an accretion center if and only if it is a centroid vertex. It is not, however, a generalization of the concept of a median since for a general graph an accretion center is not necessarily a vertex of minimum distance. A method for computing σ(v;G) based upon edge contractions is described.     

Contractible Edges in k-Connected Graphs with Some Forbidden Subgraphs

In 2001, Kawarabayashi proved that for any odd integer k ≥ 3, if a k-connected graph G is \({K^{-}_{4}}\) -free, then G has a k-contractible edge. He pointed out, by a counterexample, that this result does not hold when k is even. In this paper, we have proved the following two results on the subject: (1) For any even integer k ≥ 4, if a k-connected graph G is \({K_{4}^{-}}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge. (2) Let t ≥ 3, k ≥ 2t – 1 be integers. If a k-connected graph G is \({(K_{1}+(K_{2} \cup K_{1, t}))}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge.     

Effective analysis of integral points on algebraic curves

LetK be an algebraic number field,S?S _\t8 a finite set of valuations andC a non-singular algebraic curve overK. Letx∈K(C) be non-constant. A pointP∈C(K) isS-integral if it is not a pole ofx and |x(P)| _v >1 impliesv∈S. It is proved that allS-integral points can be effectively determined if the pair (C, x) satisfies certain conditions. In particular, this is the case if

1. x:C→P ¹ is a Galois covering andg(C)≥1;
2. the integral closure of $\bar Q$ [x] in $\bar Q$ (C) has at least two units multiplicatively independent mod $\bar Q$ *.

This generalizes famous results of A. Baker and other authors on the effective solution of Diophantine equations.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

An asymptotic version of a conjecture by Enomoto and Ota

In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let G be a graph of order n, and let n₁, n₂, …, n_k be positive integers with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} {{n}}_{{{i}}} = {{n}}\end{eqnarray*}. If σ₂(G)≥n+ k?1, then for any k distinct vertices x₁, x₂, …, x_k in G, there exist vertex disjoint paths P₁, P₂, …, P_k such that |P_i|=n_i and x_i is an endpoint of P_i for every i, 1≤i≤k. We prove an asymptotic version of this conjecture in the following sense. For every k positive real numbers γ₁, …, γ_k with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} \gamma_{{{i}}} = {{1}}\end{eqnarray*}, and for every ε>0, there exists n₀ such that for every graph G of order n≥n₀ with σ₂(G)≥n+ k?1, and for every choice of k vertices x₁, …, x_k∈V(G), there exist vertex disjoint paths P₁, …, P_k in G such that \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} |{{P}}_{{{i}}}| = {{n}}\end{eqnarray*}, the vertex x_i is an endpoint of the path P_i, and (γ_i?ε)n<|P_i|<(γ_i + ε)n for every i, 1≤i≤k. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 37–51, 2010     

Upper bounds on the signed (k, k)-domatic number

Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f ₁,f ₂, . . . ,f _d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs.