On isomorphic factorizations of circulant graphs

We investigate the conjecture that every circulant graph X admits a k‐isofactorization for every k dividing |E(X)|. We obtain partial results with an emphasis on small values of k. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 406–414, 2006     

Finding simplicial subdivisions of polytopes

Subdivisions of polytopes are described which place any chosen vertex in a (near-) minimal number of simplices. Ancillary procedures to find volumes and centroids of polytopes are indicated.     

Graphs isomorphic to their maximum matching graphs

The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.     

Complexity of projected images of convex subdivisions

Let S be a subdivision of ^d into n convex regions. We consider the combinatorial complexity of the image of the (k - 1)-skeleton of S orthogonally projected into a k-dimensional subspace. We give an upper bound of the complexity of the projected image by reducing it to the complexity of an arrangement of polytopes. If k = d − 1, we construct a subdivision whose projected image has Ω(n^(3d−2)/2) complexity, which is tight when d 4. We also investigate the number of topological changes of the projected image when a three-dimensional subdivision is rotated about a line parallel to the projection plane.     

On the size of edge-coloring critical graphs with maximum degree 4

In 1968, Vizing proposed the following conjecture: If G=(V,E) is a Δ-critical graph of order n and size m, then . This conjecture has been verified for the cases of Δ≤5. In this paper, we prove that when Δ=4. It improves the known bound for Δ=4 when n>6.     

On the mutually non isomorphic spaces,II

This note is a companion to the article On the mutually non isomorphic spaces published in this journal, in which P. Cembranos and J. Mendoza showed that is a collection of mutually non isomorphic Banach spaces [5]. We now complete the picture by allowing the non‐locally convex relatives to be part of their natural family and see that, in fact, no two members of the extended class are isomorphic. Our approach is novel in the sense that we reach the isomorphism obstructions from the perspective of bases techniques and the different convexities of the spaces, both methods being intrinsic to quasi‐Banach spaces.     

Existence of EF‐equivalent non‐isomorphic models

We prove the existence of pairs of models of the same cardinality λ which are very equivalent according to EF games, but not isomorphic. We continue the paper [4], but we do not rely on it. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the mutually non isomorphic ℓp(ℓq) spaces

We extend a result of Pe?czyński showing that {?_p(?_q): 1 ≤ p, q ≤ ∞} is a family of mutually non isomorphic Banach spaces. Some results on complemented subspaces of ?_p(?_q) are also given.     

On groups with isomorphic holomorphs

Groups with isomorphic holomorphs are said to be holomorphically isomorphic. The following problems are treated.

1. What Abelian groups have the property that their holomorphic isomorphism implies the isomorphism of the groups themselves?
2. Does holomorphic isomorphism of two groups, one of which is Abelian, imply the commutativity of the other group?

Classes of groups are selected for which the answers to these questions are positive.     

图的f-边覆盖染色

设G(V,E)是至少含有一条边的无环图,f厂是定义在V上的整值函数且对任意的v∈V,有1≤f(v)≤d(v).若边染色C使所用的每一种颜色在任一顶点v上至少出现f(v)次,则称该染色C为,f-边覆盖染色.能对图G进行,f-边覆盖k-边染色的最大颜色数k,称为图G的,f-边覆盖色数,记为X'fc(G).本文提供了一个关于X'fc(G)的Vizing型定理,使一些已有重要结论得以推广;研究了一些使X'fc(G)达到该Vizing型定理上界的几类图或函数f,还讨论了f-边覆盖染色的变型,提出了一些可进一步研究的问题.     

On the size of special class 1 graphs and (P3;k)-co-critical graphs

A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index ${\chi }^{\prime }(G)$ of G is Δ or $\mathrm{\Delta }+1$. A graph G is class 1 if ${\chi }^{\prime }(G)=\mathrm{\Delta }$, and class 2 if ${\chi }^{\prime }(G)=\mathrm{\Delta }+1$; G is Δ-critical if it is connected, class 2 and ${\chi }^{\prime }(G-e)<{\chi }^{\prime }(G)$ for every $e\in E(G)$. A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least $(n(\mathrm{\Delta }-1)+3)/2$ edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, ${\chi }^{\prime }(G+e)={\chi }^{\prime }(G)+1$ for every $e\in E(\bar{G})$. Such graphs have intimate relation to $(P_3;k)$-co-critical graphs, where a non-complete graph G is $(P_3;k)$-co-critical if there exists a k-coloring of $E(G)$ such that G does not contain a monochromatic copy of $P_3$ but every k-coloring of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $e\in E(\bar{G})$. We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all $(P_3;k)$-co-critical graphs. We prove that if G is a $(P_3;k)$-co-critical graph on $n\ge k+2$ vertices, then$e(G)\ge \frac{k}{2}(n-\lceil \frac{k}{2}\rceil -\epsilon )+\left(\begin{array}{c}\lceil k/2\rceil +\epsilon \\ 2\end{array}\right),$ where ε is the remainder of $n-\lceil k/2\rceil$ when divided by 2. This bound is best possible for all $k\ge 1$ and $n\ge \lceil 3k/2\rceil +2$.     

On posets with isomorphic interval posets

Let be a partially ordered set, Int the system of all (nonempty) intervals of partially ordered by the set-theoretical inclusion . We are interested in partially ordered sets with Int isomorphic to Int . We are going to show that they correspond to couples of binary relations on A satisfying some conditions. If is a directed partially ordered set, the only with Int isomorphic to Int are corresponding to direct decompositions of ( denotes the dual of . The present results include those presented in the paper [11] by V. Slavík. Systems of intervals, particularly of lattices, have been investigated by many authors, cf. [1]–[11].     

On multiple space subdivisions by zonotopes

This article contains P.Furtwängler's method for presenting Galois theory. To any field of rational functions belongs a group of permutations and vice versa. Given a system of roots {₁, ₂,..., _n } a field containing all relations existing between them can be defined. To this field belongs the Galois group of the given system.     

On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

On resistance of graphs

An edge-coloring of a graph G with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs.     

On isomorphic linear partitions in cubic graphs

A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. It is well known that la(G)=2 when G is a cubic graph and Wormald [N. Wormald, Problem 13, Ars Combinatoria 23(A) (1987) 332-334] conjectured that if |V(G)|≡0 (mod 4), then it is always possible to find a linear partition in two isomorphic linear forests. Here, we give some new results concerning this conjecture.