Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

On disjointly representable sets

A system of setsE ₁,E ₂, ...,E _k ⊂X is said to be disjointly representable if there existx ₁,x ₂, ...,x _k teX such thatx _i teE _j ⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem [16] for uniform set-systems. Dedicated to Paul Erdős on his seventieth birthday     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.     

Some properties of multivariate extreme value distributions and multivariate tail equivalence

Summary Denote byH ak-dimensional extreme value distribution with marginal distributionH _i (x)=Λ(x)=exp(−e ^−x ),x∈R ¹. Then it is proved thatH(x)=Λ(x ₁)...Λ(x _k ) for anyx=(x ₁, ...,x _k ) ∈R ^k , if and only if the equation holds forx=(0,...,0). Next some multivariate extensions of the results by Resnick (1971,J. Appl. Probab.,8, 136–156) on tail equivalence and asymptotic distributions of extremes are established.     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

Cohen-macaulay bipartite graphs

Let G be a graph on the vertex set V={x ₁, ..., x _n}. Let k be a field and let R be the polynomial ring k[x ₁, ..., x _n]. The graph ideal I(G), associated to G, is the ideal of R generated by the set of square-free monomials x _ix_j so that x _i, is adjacent to x _j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring. Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs. Partially supported by COFAA-IPN, CONACyT and SNI, México.     

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     

Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form f([`(x)]) = ?<sub>i = 1</sub><sup>k</sup> h<sub>i</sub> ([`(x)]) ·g_i ([`(x)])f(\bar x) = \sum\nolimits_{i = 1}^k {h_i (\bar x) \cdot g_i (\bar x)} , where each h _i is a polynomial that depends on only ρ linear functions, and each g _i is a product of linear functions (when h _i = 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as ΣΠΣ(k) circuits, but the general case is much richer). When max _i (deg(h _i · g _i )) = d we say that f is computable by a ΣΠΣ(k; d;ρ) circuit. We obtain the following results.

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

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.     

On the sets of branch points of mappings more general than quasiregular

It is shown that if a point x ₀ ∊ ℝ ⁿ , n ≥ 3, is an essential isolated singularity of an open discrete Q-mapping f : D → [`(\mathbb R<sup>n</sup>)] \overline {\mathbb {R}^n} , B <sub>f</sub> is the set of branch points of f in D; and a point z <sub>0</sub> ∊ [`(\mathbb Rⁿ)] \overline {\mathbb {R}^n} is an asymptotic limit of f at the point x ₀; then, for any neighborhood U containing the point x ₀; the point z ₀ ∊ [`(f( B<sub>f</sub> ?U ))] \overline {f\left( {B_f \cap U} \right)} provided that the function Q has either a finite mean oscillation at the point x <sub>0</sub> or a logarithmic singularity whose order does not exceed n − 1: Moreover, for n ≥ 2; under the indicated conditions imposed on the function Q; every point of the set [`(\mathbb Rⁿ)] \overline {\mathbb {R}^n} \ f(D) is an asymptotic limit of f at the point x ₀. For n ≥ 3, the following relation is true: [`(\mathbbR<sup>n</sup> )] \f( D ) ì [`(f B_f )] \overline {\mathbb{R}^n } \backslash f\left( D \right) \subset \overline {f\,B_f } . In addition, if ￥ ? f( D ) \infty \notin f\left( D \right) , then the set f B _f is infinite and x₀ ? [`(B_f )] x_0 \in \overline {B_f } .     

Embedding ofl ∞ k in finite dimensional Banach spaces

Letx ₁,x ₂, ...,x _n ben unit vectors in a normed spaceX and defineM _n =Ave{‖Σ _i=1 ⁿ ε₁ x _i ‖:ε₁=±1}. We prove that there exists a setA⊂{1, ...,n} of cardinality such that {x _i } _i∈A is 16M _n -isomorphic to the natural basis ofl _∞ ^k . This result implies a significant improvement of the known results concerning embedding ofl _∞ ^k in finite dimensional Banach spaces. We also prove that for every ∈>0 there exists a constantC(∈) such that every normed spaceX _n of dimensionn either contains a (1+∈)-isomorphic copy ofl ₂ ^m for somem satisfying ln lnm≧1/2 ln lnn or contains a (1+∈)-isomorphic copy ofl _∞ ^k for somek satisfying ln lnk>1/2 ln lnn−C(∈). These results follow from some combinatorial properties of vectors with ±1 entries. The contribution of the first author to this paper forms part of his Ph.D. Thesis written under the supervision of Prof. M. A. Perles from the Hebrew University.     

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.     

Multiplicative isometries on the Smirnov class

We show that T is a surjective multiplicative (but not necessarily linear) isometry from the Smirnov class on the open unit disk, the ball, or the polydisk onto itself, if and only if there exists a holomorphic automorphism Φ such that T(f)=f ○ Φ for every class element f or T(f) = [`(f<sup>°</sup> [`(j)] )]\overline {f^\circ \bar \varphi } for every class element f, where the automorphism Φ is a unitary transformation in the case of the ball and Φ(z ₁, ..., z _n ) = (l₁ z_i1 ,...,l_n z_in )(\lambda _1 z_{i_1 } ,...,\lambda _n z_{i_n } ) for |λ _j | = 1, 1 ≤ j ≤ n, and (i ₁; ..., i _n )is some permutation of the integers from 1through n in the case of the n-dimensional polydisk.     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.     

Almost 2-Homogeneous Graphs and Completely Regular Quadrangles

Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ _i  = |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application, we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph. This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion of Science.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS

§1　IntroductionGraphs considered in this paper are finite and simple.For a graph G,its vertex setandedge set are denoted by V(G) and E(G) ,respectively.If vertices u and v are connected inG,the distance between u and v,denoted by d G(u,v) ,is the length ofa shortest(u,v) -pathin G.The diameter of a connected graph G is the maximum distance between two verticesof G.For X V(G) ,the neighbor set NG(X) of X is defined byNG(X) ={ y∈V(G) \X:there is x∈X such thatxy∈E(G) } .NG({ x} )…     

On pair correlations and Hausdorff dimension

We consider a system of “generalised linear forms” defined at a point x = (x _{(i, j)}) in a subset of R ^d by

Large sample nonparametric rejection of outlying observations

1. Summary Letx ₁≦, ..., ≦x _n be independent observations from continuous populations. The null hypothesis,H ₀, is that these observations are a sample. The alternative hypothesis is that thei smallest observations are too small (or that thei largest observations are too large) to be consistent withH ₀. Herei is a small number and should be specified without knowledge of the observation values. The common population hypothesized for the null case is assumed to be well-behaved but no specific assumptions are made about its shape. The alternative that thei smallest observations are too small is accepted if a statistic of the formx _i−(1+A)x _i+1+Ax _k is negative, whereA>0,k is the largest integer contained ini+√2n, andn is sufficiently large. Similarly, the alternative that thei largest observations are too large is accepted ifx _n+1−i −(1+A)x _n−i+Ax _n+1−k is positive. Two-sided tests are obtained as combinations of these one-sided tests. ForA suitably chosen, an approximate upper bound for the significance level of a test is evaluated from Techebycheff’s inequality. Using this relation, the value ofA is expressed as a function ofi, n, and the significance level upper bound. For fixed population shapes, these tests have powers that tend to unity for the case wheren−i of the populations are the same and the minimum difference between the median of this common population and the medians of the other populations increases in the appropriate direction The results of this paper may be useful in population statistics, operations research, and other applied fields.