Highly parity linked graphs

A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x ₁,x ₂, …, x _k ,y ₁,y ₂, …, y _k , G contains k pairwise disjoint paths P ₁, …, P _k such that P _i joins x _i and y _i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P ₁, …, P _k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists.     

High Connectivity Keeping Sets In <Emphasis Type="Italic">n</Emphasis>-Connected Graphs

It is proved that for every positive integer k, every n-connected graph G of sufficiently large order contains a set W of k vertices such that G—W is (n-2)-connected. It is shown that this does not remain true if we add the condition that G(W) is connected.     

Fan-type theorem for path-connectivity

A graphG is said to bek-path-connected if every pair of distinct vertices inG are joined by a path of length at leastk. We prove that if max{deg _G ^x , deg _G ^y }k for every pair of verticesx,y withd _G (x,y)=2 in a 2-connected graphG, whered _G (x,y) is the distance betweenx andy inG, thenG isk-path-connected.     

Graph Connectivity After Path Removal

Let G be a graph and u, v be two distinct vertices of G. A u—v path P is called nonseparating if G—V(P) is connected. The purpose of this paper is to study the number of nonseparating u—v path for two arbitrary vertices u and v of a given graph. For a positive integer k, we will show that there is a minimum integer (k) so that if G is an (k)-connected graph and u and v are two arbitrary vertices in G, then there exist k vertex disjoint paths P ₁[u,v], P ₂[u,v], . . ., P _k [u,v], such that G—V (P _i [u,v]) is connected for every i (i = 1, 2, ..., k). In fact, we will prove that (k) 22k+2. It is known that (1) = 3.. A result of Tutte showed that (2) = 3. We show that (3) = 6. In addition, we prove that if G is a 5-connected graph, then for every pair of vertices u and v there exists a path P[u, v] such that G—V(P[u, v]) is 2-connected.* Supported by NSF grant No. DMS-0070059 Supported by ONR grant N00014-97-1-0499 Supported by NSF grant No. 9531824     

The minimum span of L(2,1)-labelings of certain generalized Petersen graphs

In the classical channel assignment problem, transmitters that are sufficiently close together are assigned transmission frequencies that differ by prescribed amounts, with the goal of minimizing the span of frequencies required. This problem can be modeled through the use of an L(2,1)-labeling, which is a function f from the vertex set of a graph G to the non-negative integers such that |f(x)-f(y)|? 2 if xand y are adjacent vertices and |f(x)-f(y)|?1 if xand y are at distance two. The goal is to determine the λ-number of G, which is defined as the minimum span over all L(2,1)-labelings of G, or equivalently, the smallest number k such that G has an L(2,1)-labeling using integers from {0,1,…,k}. Recent work has focused on determining the λ-number of generalized Petersen graphs (GPGs) of order n. This paper provides exact values for the λ-numbers of GPGs of orders 5, 7, and 8, closing all remaining open cases for orders at most 8. It is also shown that there are no GPGs of order 4, 5, 8, or 11 with λ-number exactly equal to the known lower bound of 5, however, a construction is provided to obtain examples of GPGs with λ-number 5 for all other orders. This paper also provides an upper bound for the number of distinct isomorphism classes for GPGs of any given order. Finally, the exact values for the λ-number of n-stars, a subclass of the GPGs inspired by the classical Petersen graph, are also determined. These generalized stars have a useful representation on Möebius strips, which is fundamental in verifying our results.     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

On k -diameter of k -connected graphs

Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d _k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d _k (G). For a fixed positive integer d, some conditions to insure d _k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d _k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).     

On approximation of approximately generalized quadratic functional equation via Lipschitz criteria

Abstract

Let G be an Abelian group with a metric d and E ba a normed space. For any f : G → E we define the generalized quadratic di?erence of the function f by the formula

Q_k f (x, y) := f (x + ky) + f (x ? ky) ? f (x + y) ? f (x ? y) ? 2(k² ? 1)f (y)

for all x, y ∈ G and for any integer k with k ≠ 1, ?1. In this paper, we achieve the general solution of equation Q_k f (x, y) = 0, after it, we show that if Q_k f is Lipschitz, then there exists a quadratic function K : G → E such that f ? K is Lipschitz with the same constant. Moreover, some results concerning the stability of the generalized quadratic functional equation in the Lipschitz norms are presented. In the particular case, if k = 0 we obtain the main result that is in [7].     

Reductions of 3-connected graphs with minimum degree at least four

We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x₁, x₂, x₃, x₄} and x₁x₂, x₃x₄ ∈ E(G) such that the graph (G ? x)/x₁x₂/x₃x₄ obtained by contraction of edges x₁x₂ and x₃x₄ in G – x is a 3-connected graph of minimum degree at least 4.

Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions.     

A comparative study of functional equations characterising sine and cosine

A comparative study of the functional equationsf(x+y)f(x–y)=f ²(x)–f ²(y),f(y){f(x+y)+f(x–y)}=f(x)f(2y) andf(x+y)+f(x–y)=2f(x){1–2f ²(y/2)} which characterise the sine function has been carried out. The zeros of the functionf satisfying any one of the above equations play a vital role in the investigations. The relation of the equationf(x+y)+f(x–y)=2f(x){1–2f ²(y/2)} with D'Alembert's equation,f(x+y)+f(x–y)=2f(x)f(y) and the sine-cosine equationg(x–y)=g(x)g(y) +f(x)f(y) has also been investigated.     

Very Asymmetric Marking Games

We investigate a competitive version of the coloring number of a graph G = (V, E). For a fixed linear ordering L of V let s (L) be one more than the maximum outdegree of G when G is oriented so that x ← y if x < _L y. The coloring number of G is the minimum of s (L) over all such orderings. The (a, b)-marking game is played on a graph G = (V, E) as follows. At the start all vertices are unmarked. The players, Alice and Bob, take turns playing. A play consists of Alice marking a unmarked vertices or Bob marking b unmarked vertices. The game ends when there are no remaining unmarked vertices. Together the players create a linear ordering L of V defined by x < y if x is marked before y. The score of the game is s (L). The (a, b)-game coloring number of G is the minimum score that Alice can obtain regardless of Bob’s strategy. The usual (1, 1)-marking game is well studied and there are many interesting results. Our main result is that if G has an orientation with maximum outdegree k then the (k, 1)-game coloring number of G is at most 2k + 2. This extends a fundamental result on the (1, 1)-game coloring number of trees. We also construct examples to show that this bound is tight for many classes of graphs. Finally we prove bounds on the (a, 1)-game coloring number when a < k.     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

Existence and Uniqueness of Strong Solutions for a Class of Quasi‐Linear Hyperbolic Equations with Order Degeneration

Let k(y) > 0, 𝓁(y) > 0 for y > 0, k(0) = 𝓁(0) = 0 and lim_{y → 0}k(y)/𝓁(y) exists; then the equation L(u) ≔ k(y)u_xx – ∂_y(𝓁(y)u_y) + a(x, y)u_x = f(x, y, u) is strictly hyperbolic for y > 0 and its order degenerates on the line y = 0. Consider the boundary value problem Lu = f(x, y, u) in G, u|_AC = 0, where G is a simply connected domain in ℝ² with piecewise smooth boundary ∂G = AB∪AC∪BC; AB = {(x, 0) : 0 ≤ x ≤ 1}, AC : x = F(y) = ∫^y₀(k(t)/𝓁(t))^1/2dt and BC : x = 1 – F(y) are characteristic curves. Existence of generalized solution is obtained by a finite element method, provided f(x, y, u) satisfies Carathéodory condition and |f(x, y, u)| ≤ Q(x, y) + b|u| with Q ∈ L²(G), b = const > 0. It is shown also that each generalized solution is a strong solution, and that fact is used to prove uniqueness under the additional assumption |f(x, y, u₁) – f(x, y, u₂| ≤ C|u₁ – u₂|, where C = const > 0.     

Subpancyclicity of line graphs and degree sums along paths

A graph is called subpancyclic if it contains a cycle of length ? for each ? between 3 and the circumference of the graph. We show that if G is a connected graph on n?146 vertices such that d(u)+d(v)+d(x)+d(y)>(n+10/2) for all four vertices u,v,x,y of any path P=uvxy in G, then the line graph L(G) is subpancyclic, unless G is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that L(G) is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.     

Disjoint cycles in digraphs

We show that, for each natural numberk, these exists a (smallest) natural numberf(k) such that any digraph of minimum outdegree at leastf(k) containsk disjoint cycles. We conjecture thatf(k)=2k−1 and verify this fork=2 and we show that, for eachk≧3, the determination off(k) is a finite problem. Dedicated to Paul Erdős on his seventieth birthday     

A characterization of panconnected graphs satisfying a local ore-type condition

It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.     

A wavelike functional equation of Pexider type

Summary. Let (G, +) and (H, +) be abelian groups such that the equation 2u = v 2u = v is solvable in both G and H. It is shown that if f₁, f₂, f₃, f₄, : G ×G ? H f_1, f_2, f_3, f_4, : G \times G \longrightarrow H satisfy the functional equation f₁(x + t, y + s) + f₂(x - t, y - s) = f₃(x + s, y - t) + f₄(x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , then f₁, f₂, f₃, and f₄ are given by f₁ = w + h, f₂ = w - h, f₃ = w + k, f₄ = w - k where w : G ×G ? H w : G \times G \longrightarrow H is an arbitrary solution of f (x + t, y + s) + f (x - t, y - s) = f (x + s, y - t) + f (x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , and h, k : G ×G ? H h, k : G \times G \longrightarrow H are arbitrary solutions of D_y,t³g(x,y) = 0 \Delta_{y,t}^{3}g(x,y) = 0 and D_x,t³g(x,y) = 0 \Delta_{x,t}^{3}g(x,y) = 0 for all x, y, s, t ? G x, y, s, t \in G .     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

Mader’s Conjecture On Extremely Critical Graphs

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.     

（g,f）-FACTORS WITH SPECIAL PROPERTIES IN BIPARTITE （mg,mf）-GRAPHS

Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x). In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.