Polynomials with graphs of maximum length

In this paper we find the pairs of functionsg, G (g<G) such that the maximum length of the graph of polynomials of given degree contained betweeng andG is attained on one of the two snakes generated by the functionsg andG. Translated fromMatematicheskie Zametki, Vol. 65, No. 1, pp. 61–69, January, 1999.     

Association Schemes and Fusion Algebras (An Introduction)

We introduce the concept of fusion algebras at algebraic level, as a purely algebraic concept for the fusion algebras which appear in conformal field theory in mathematical physics. We first discuss the connection between fusion algebras at algebraic level and character algebras, a purely algebraic concept for Bose-Mesner algebras of association schemes. Through this correspondence, we establish the condition when the matrix S of a fusion algebra at algebraic level is unitary or symmetric. We construct integral fusion algebras at algebraic level, from association schemes, in particular from group association schemes, whose matrix S is unitary and symmetric. Finally, we consider whether the modular invariance property is satisfied or not, namely whether there exists a diagonal matrix T satisfying the condition (ST)³ = S ². We prove that this property does not hold for some integral fusion algebras at algebraic level coming from the group association scheme of certain groups of order 64, and we also prove that the (nonintegral) fusion algebra at algebraic level obtained from the Hamming association scheme H(d, q) has the modular invariance property.     

Berge graphs with chordless cycles of bounded length

A graph is called weakly triangulated if it contains no chordless cycle on five or more vertices (also called hole) and no complement of such a cycle (also called antihole). Equivalently, we can define weakly triangulated graphs as antihole-free graphs whose induced cycles are isomorphic either to C₃ or to C₄. The perfection of weakly triangulated graphs was proved by Hayward [Hayward, J Combin Theory B. 39 (1985), 200–208] and generated intense studies to efficiently solve, for these graphs, the classical NP-complete problems that become polynomial on perfect graphs. If we replace, in the definition above, the C₄ by an arbitrary C_p (p even, at least equal to 6), we obtain new classes of graphs whose perfection is shown in this article. In fact, we prove a more general result: for any even integer p ≥ 6, the graphs whose cycles are isomorphic either to C₃ or to one of C_p, C_p+2, …, C_{2p 6} are perfect. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 73–79, 1999     

On the extendability of certain semi-Cayley graphs of finite abelian groups

A connected graph Γ with at least 2n+2 vertices is said to be n-extendable if every matching of size n in Γ can be extended to a perfect matching. The aim of this paper is to study the 1-extendability and 2-extendability of certain semi-Cayley graphs of finite abelian groups, and the classification of connected 2-extendable semi-Cayley graphs of finite abelian groups is given. Thus the 1-extendability and 2-extendability of Cayley graphs of non-abelian groups which can be realized as such semi-Cayley graphs of abelian groups can be deduced. In particular, the 1-extendability and 2-extendability of connected Cayley graphs of generalized dicyclic groups and generalized dihedral groups are characterized.     

Downwind Gauß-Seidel Smoothing for Convection Dominated Problems

In the case of convection dominated problems, multigrid methods require an appropriate smoothing to ensure robustness. As a first approach we discuss a Gauss–Seidel smoothing with a correct numbering of the unknowns and if necessary a special block partitioning. Numerical experiments show that, in the case of general convection directions, the multigrid algorithms obtained in this way have the same properties as in the model situation. If the graph arising from the convection part is acyclic, we describe a numbering algorithm which is valid for all spatial dimensions. Cycles give rise to special blocks for a blockwise Gauss–Seidel smoothing. We describe an algorithm for the two-dimensional case. The proposed algorithm requires a computational work of optimal order (linear in the size of the problem). © 1997 by John Wiley & Sons, Ltd.     

On Clique-Transversals and Clique-Independent Sets

A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. A clique-independent set is a subset of pairwise disjoint cliques of G. Denote by _C (G) and _C (G) the cardinalities of the minimum clique-transversal and maximum clique-independent set of G, respectively. Say that G is clique-perfect when _C (H)= _C (H), for every induced subgraph H of G. In this paper, we prove that every graph not containing a 4-wheel nor a 3-fan as induced subgraphs and such that every odd cycle of length greater than 3 has a short chord is clique-perfect. The proof leads to polynomial time algorithms for finding the parameters _C (G) and _C (G), for graphs belonging to this class. In addition, we prove that to decide whether or not a given subset of vertices of a graph is a clique-transversal is Co-NP-Complete. The complexity of this problem has been mentioned as unknown in the literature. Finally, we describe a family of highly clique-imperfect graphs, that is, a family of graphs G whose difference _C (G)– _C (G) is arbitrarily large.     

Sources and Sinks in Comparability Graphs

We prove that a subset S of vertices of a comparability graph G is a source set if and only if each vertex of S is a source and there is no odd induced path in G between two vertices of S. We also characterize pairs of subsets corresponding to sources and sinks, respectively. Finally, an application to interval graphs is obtained.     

Randomized broadcast in networks

In this paper we study the rate at which a rumor spreads through an undirected graph. This study has two important applications in distributed computation: in simple, robust and efficient broadcast protocols, and in the maintenance of replicated databases.     

Unique factorization of compositive hereditary graph properties

A graph property is any class of graphs that is closed under isomorphisms. A graph property P is hereditary if it is closed under taking subgraphs; it is compositive if for any graphs G1, G2 ∈ P there exists a graph G ∈ P containing both G1 and G2 as subgraphs. Let H be any given graph on vertices v1, . . . , vn, n ≥ 2. A graph property P is H-factorizable over the class of graph properties P if there exist P 1 , . . . , P n ∈ P such that P consists of all graphs whose vertex sets can be partitioned into n parts, possibly empty, satisfying: 1. for each i, the graph induced by the i-th non-empty partition part is in P i , and 2. for each i and j with i = j, there is no edge between the i-th and j-th parts if vi and vj are non-adjacent vertices in H. If a graph property P is H-factorizable over P and we know the graph properties P 1 , . . . , P n , then we write P = H [ P 1 , . . . , P n ]. In such a case, the presentation H[ P 1 , . . . , P n ] is called a factorization of P over P. This concept generalizes graph homomorphisms and (P 1 , . . . , P n )-colorings. In this paper, we investigate all H-factorizations of a graph property P over the class of all hered- itary compositive graph properties for finite graphs H. It is shown that in many cases there is exactly one such factorization.     

Filling of a given boundary by p-gons and related problems

We consider here (p,s)-polycycles (3ps) i.e. plane graphs, such that all interior faces are p-gons, all interior vertices are s-valent and any vertex of the boundary (i.e. the exterior face) has valency within [2,s]. The boundary sequence of a (p,s)-polycycle P is the sequence b(P) enumerating, up to a cyclic shift or reversal, the consecutive valencies of vertices of the boundary. We show that the values p=3,4 are the only ones, such that the boundary sequence defines its (p,3)-filling (i.e. a (p,3)-polycycle with given boundary) uniquely.Also we give new results in the enumeration of maps M_n(p,q) (i.e. plane 3-valent maps with only p- and q-gonal faces, such that the q-gons are organized in an n-ring) and two of their generalizations.Both problems are similar (3-valent filling by p-gons of a boundary or of a ring of q-gons) and the same programs were used for both computations.