Characterization of H(n, q) by the parameters

Distance-regular graphs which have the same parameters as the Hamming scheme H(n, q) are classified. If q ≠ 4, H(n, q) is the only such graph. If q = 4, there are precisely $\text{[}\text{n}\text{2}\text{]}$ (isomorphism classes of) such graphs other than H(n, q).     

On the spectral radius of bicyclic graphs with n vertices and diameter d

Bicyclic graphs are connected graphs in which the number of edges equals the number of vertices plus one. In this paper we determine the graph with the largest spectral radius among all bicyclic graphs with n vertices and diameter d. As an application, we give first three graphs among all bicyclic graphs on n vertices, ordered according to their spectral radii in decreasing order.     

On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

Minimum number of edges in graphs that are both P2- and Pi-connected

A simple graph with n vertices is called P_i-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P₂- and P_i-connected are obtained. Namely if $\text{i?}\text{1}\text{2}\text{(n+1)}$, then |E(G)|?((4i?5)/(2i?2))(n?1), and if $\text{i >}\text{1}\text{2}\text{(n+ 1)}$, then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former.     

Diagonalizing matrices over C(X)

A complete characterization of those compact Hausdorff spaces is given such that for every n, each normal element in the algebra C(X)?M_n of continuous functions from X to $\text{M}$_n can be continuously diagonalized. The conditions are that X be a sub-Stonean space with dim X ? 2 and carries no nontrivial G-bundles over any closed subset, for G a symmetric group or the circle group. In particular, diagonalization is assured on every totally disconnected sub-Stonean space, but also on connected spaces of the form β(Y)/Y, where Y is a simply-connected (noncompact) graph.     

Almost resolvable decomposition of Kn1

In this paper, we show that the complete symmetric directed graph with n vertices $\text{K}{}_{\mathrm{n}}{}^1$ admits an almost resolvable decomposition into TT₃ (the transitive tournament on 3 vertices) or C₃ (the directed cycle of length 3) if and only if n ≡ 1(mod 3).     

Decomposition de Km+Kn en cycles hamiltoniens

Let K_m be the complete graph of order m. We prove that the cartesian sum K_m+K_n can be decomposed into $\text{1}\text{2}$(m+n?2) hamiltonian cycles if m+n is even and into $\text{1}\text{2}$(m+n?3) hamiltonian cycles and a perfect matching if m+n is odd.     

An O(n2log n) parallel max-flow algorithm

A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented. Its depth is $\text{O(}\text{n}{}^3\text{(}\text{log}\text{n)}\text{p)}$, where p (p ≤ n) is the number of processors used. This problem seems to be more involved than most of the problems for which efficient parallel algorithms exist. The parallel algorithm induces a new rather simple sequential O(n³) algorithm. This algorithm is very much parallel oriented. It is quite difficult to conceive and analyze it, if one is restricted to the sequential point of view.     

On the signless Laplacian spectral radius of graphs with cut vertices

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.     

On the minimum order of graphs with given semigroup

Denote by M(n) the smallest positive integer such that for every n-element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that $\text{2}\text{(1 + o(1))n}\text{log}{}_2\text{n}\text{≤M(n)≤n ·}\text{2n}\text{+ O(n)}$. Moreover, for almost all n-element monoids M there is a graph G with at most 12 · n · log₂n + n vertices such that End(G) is isomorphic to M.     

The graphs G(n, k) of the Johnson Schemes are unique for n ≥ 20

Let G(n, k) denote the graph of the Johnson Scheme J(n, k), i.e., the graph whose vertices are all k-subsets of a fixed n-set, with two vertices adjacent if and only if their intersection is of size k ? 1. It is known that G(n, k) is a distance regular graph with diameter k. Much work has been devoted to the question of whether a distance regular graph with the parameters of G(n, k) must isomorphic to G(n, k). In this paper, this question is settled affirmatively for n ≥ 20. In fact the result is proved with weaker conditions.     

On complementary graphs with no isolated vertices

Let $\text{G}$ denote the complement of a graph G, and x(G), β₁(G), β₄(G), α₀(G), α₁(G) denote respectively the chromatic number, line-independence number, point-independence number, point-covering number, line-covering number of G, Nordhaus and Gaddum showed that for any graph G of order $\text{p}\text{, {2√p} ? x(G) + x(}\text{G}\text{) ? p + 1}\text{and p}\text{? x(G)·x(}\text{G}\text{) ? [(}\text{1}\text{2}\text{(p + 1))}{}^2\text{]}$. Recently Chartrand and Schuster have given the corresponding inequalities for the independence numbers of any graph G. However, combining their result with Gallai's well known formula β₁(G) + α₁(G) = ?, one is not deduce the analogous bounds for the line-covering numbers of $\text{G}\text{and}\text{G}$, since Gallai's formula holds only if G contains no isolated vertex. The purpose of this note is to improve the results of Chartland and Schuster for line-independence numbers for graphs where both $\text{G}\text{and}\text{G}$ contain no isolated vertices and thereby allowing us to use Gallai's formula to get the corresponding bounds for the line-covering numbers of G.     

G-decomposition of Kn, where G has four vertices or less

The complete graph K_n, is said to have a G-decomposition if it is the union of edge disjoint subgraphs each isomorphic to G. The set of values of n for which K_n has a G-decomposition is determined if G has four vertices or less.     

Some properties of irreducible coverings by cliques of complete multipartite graphs

In this paper some recursion formulas and asymptotic properties are derived for the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite (labeled) graphs K_p,q. The problem of determining numbers N(p, q) has been raised by I. Tomescu (dans “Logique, Automatique, Informatique,” pp. 269–423, Ed. Acad. R.S.R., Bucharest, 1971). A result concerning the asymptotic behavior of the number of irreducible coverings by cliques of q-partite complete graphs is obtained and it is proved that , $\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{log}\text{M(n))}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 3}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and $\text{lim}{}_{\mathrm{n\to \infty }}\text{C(n)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{(}\text{n}\text{ln}\text{n)}\text{=}\text{1}\text{e}$, where I(n) and M(n) are the maximal numbers of irreducible coverings, respectively, coverings by cliques of the vertices of an n-vertex graph, and C(n) is the maximal number of minimal colorings of an n-vertex graph. It is also shown that maximal number of irreducible coverings by n ? 2 cliques of the vertices of an n-vertex graph (n ≥ 4) is equal to 2^n?2 ? 2 and this number of coverings is attained only for K_2,n?2 and the value of $\text{lim}{}_{\mathrm{n\to \infty }}\text{I(n, n ? k)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ is obtained, where I(n, n ? k) denotes the maximal number of irreducible coverings of an n-vertex graph by n ? k cliques.     

Factorizing the complete graph into factors with large star number

The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that $\text{c}{}_1{}^{\mathrm{n}}\text{k ≤ f(n, k) < c}{}_2{}^{\mathrm{n}}\text{k}$.     

n-Tuple colorings and associated graphs

The n-tuple graph coloring, which assigns to each vertex n colors, is defined together with its respective chromatic number x_n. It is proved that these numbers satisfy the inequality x_n ≥ 2 + x_n?1, and that equality holds only for bipartite graphs. Graphs $\text{G}{}_{\mathrm{n}}{}^{\mathrm{m}}$ are defined which play the same role for the n-tuple coloring that K_m plays for the conventional coloring. The chromatic numbers of various classes of graphs are also calculated.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

The validity of the strong perfect-graph conjecture for (K4−e)-free graphs

Berge's strong perfect-graph conjecture states that a graph is perfect iff it has neither C_2n+1 nor $\text{C}{}_{\mathrm{2n+1}}$, n ≥ 2 as an induced subgraph. In this note we establish the validity of this conjecture for (K₄?e)-free graphs.     

Computing a perfect strategy for n × n chess requires time exponential in n

It is proved that a natural generalization of chess to an n × n board is complete in exponential time. This implies that there exist chess positions on an n × n chessboard for which the problem of determing who can win from that position requires an amount of time which is at least exponential in $\text{n}$.     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.