Search

Abstract: Let be a graph. For , let denote the maximum value of the degree sums of the subsets of of order . In this paper, we prove the following two results. (1) Let be a 2-connected graph. If for every independent set of order , then has a cycle of length at least . (2) Let be a 2-connected graph and a subset of . If for every independent set of order in , then has a cycle that includes every vertex of . This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles. [Copyright &y& Elsevier]

Abstract: Let be a simple graph on vertices. In this paper, we prove that if satisfies the condition that for each , then has no nowhere-zero 3-flow if and only if is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices. [Copyright &y& Elsevier]

Abstract: An edge of a -connected graph is said to be -contractible if its contraction yields a -connected graph. A non-complete -connected graph possessing no -contractible edges is called contraction-critical -connected. Let be a contraction-critical 7-connected graph with vertices, and the set of vertices of degree 7 in . In this paper, we prove that , which improves the result proved by Ando, Kaneko and Kawarabayashi. In the meantime, we obtain that for any vertex in a contraction-critical 7-connected graph there is a vertex such that the distance between and is at most 2, and thus extends a result of Su and Yuan. We present a family of contraction-critical 7-connected graphs in which is independent. [Copyright &y& Elsevier]

Abstract: Let be a graph and be a vertex of . We consider the following operation: add a new vertex such that does not distinguish any two vertices which are not distinguished by . We call this operation a one-vertex extension. Adding a true twin, a false twin or a pendant vertex are cases of one-vertex extensions. Here we are interested in graph classes defined by a subset of allowed one-vertex extension. Examples are trees, cographs and distance-hereditary graphs. We give a complete classification of theses classes with respect to their clique-width. We also introduce a new graph parameter called the modular-width, and we give a relation with the clique-width. [Copyright &y& Elsevier]

Abstract: In this paper we study representations of permutation groups as automorphism groups of colored graphs and supergraphs. In particular, we consider how such representations for various products of permutation groups can be obtained from representations of factors and how the degree of complexity increases in such constructions. [Copyright &y& Elsevier]

Abstract: The vertex-distinguishing index of a graph G is the minimum number of colours required to properly colour the edges of G in such a way that any two vertices are incident with different sets of colours. We consider this parameter for some regular graphs. Moreover, we prove that for any graph, the value of this invariant is not changed if the colouring above is, in addition, required to be equitable. [Copyright &y& Elsevier]

Abstract: A distance-colouring relative to distance p of a graph is a mapping of V in a set of colours in such a way that any two vertices of G of distance not greater than p have distinct colours. The purpose of this paper is to give a survey of the results related to the distance-colouring of graphs introduced in 1969. [Copyright &y& Elsevier]

Abstract: It was proved by Fronček, Jerebic, Klavžar, and Kovář that if a complete bipartite graph with a perfect matching removed can be covered by k bicliques, then . We give a slightly simplified proof and we show that the result is tight. Moreover, we use the result to prove analogous bounds for coverings of some other classes of graphs by bicliques. [Copyright &y& Elsevier]

Abstract: We give a simple alternative proof of the representation theorem of all genus two 3-manifolds by a 6-parameter family of integers, due to Casali and Grasselli (see [M.R. Casali, A catalogue of the genus two 3-manifolds, Atti. Sem. Mat. Fis. Univ. Modena 37 (1989) 207–236]; [M.R. Casali, L. Grasselli, 2-Symmetric crystallizations and 2-fold branched coverings of , Discrete Math. 87 (1991) 9–22]). Our approach is different from that of the quoted papers, and it is based on the concept of extended Heegaard diagram. This permits to obtain new topological meanings of the arithmetic conditions which the parameters must satisfy for representing closed manifolds. Some applications and results on some homology spheres of genus 2 complete the paper. [Copyright &y& Elsevier]

Abstract: In this paper we study the elementary properties of double graphs, i.e. of graphs which are the direct product of a simple graph with the graph obtained by the complete graph adding a loop to each vertex. [Copyright &y& Elsevier]

Abstract: Let denote the graph on a vertices with edges between every pair of vertices. Take p copies of this graph , and join each pair of vertices in different copies with edges. The resulting graph is denoted by , a graph that was of particular interest to Bose and Shimamoto in their study of group divisible designs with two associate classes. The existence of z-cycle decompositions of this graph have been found when . In this paper we consider resolvable decompositions, finding necessary and sufficient conditions for a 4-cycle factorization of (when is even) or of minus a 1-factor (when is odd) whenever a is even. [Copyright &y& Elsevier]

Abstract: In this paper all Veronesean caps of projective spaces of finite dimension over skewfields are classified. More precisely, if , K a skewfield, contains a Veronesean cap X, then K is a field and X is either a Veronese variety or a projection of a Veronese variety. This result extends analogous theorems of Mazzocca and Melone [Caps and Veronese varieties in projective Galois spaces. Discrete Math. 48 (1984) 243–252] and Thas and Van Maldeghem [Classification of finite Veronesean caps, European J. Combin. 25(2) (2004) 275–285] for finite projective spaces. [Copyright &y& Elsevier]

Abstract: The well known correspondence between even cycles of an undirected graph and polynomials in a binomial ideal associated to a graph is extended to odd cycles and polynomials in another binomial ideal. Other binomial ideals associated to an undirected graph are also introduced. The results about them with topics on monomial ideals are used in order to show decision procedures for bipartite graphs, minimal vertex covers, cliques, edge covers and matchings with algebraic tools. All such procedures are implemented in Maple 9.5. [Copyright &y& Elsevier]

Abstract: We present all possible distributions of 3-kings in 3-partite tournaments with at most one transmitter. [Copyright &y& Elsevier]

Abstract: In this paper the complementary hyperstructure obtained from a multiplicative hyperring is considered. Furthermore a characterization for such hyperstructures obtained starting from a strongly distributive multiplicative hyperring is given. [Copyright &y& Elsevier]

Abstract: A graph is called equipackable if every maximal packing in it is also maximum. This generalizes randomly packable graphs. We survey known results both on randomly packable graphs and on equipackable graphs. As a new result is given a characterization of -equipackable graphs with all valencies at least two. [Copyright &y& Elsevier]

Abstract: For a connected graph , an edge set is a k-restricted-edge-cut if is disconnected and every component of has at least k vertices. The cardinality of a minimum k-restricted-edge-cut is the k-restricted-edge-connectivity of G, denoted by . In this paper, we study sufficient conditions for to be optimal, especially when and 3. [Copyright &y& Elsevier]

Abstract: By Petersen''s theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most components. This upper bound is best possible. [Copyright &y& Elsevier]

Abstract: In this paper, we study the crossing number of the circulant graph and prove that for . [Copyright &y& Elsevier]

Abstract: We show that a set of graphs has bounded tree-width or bounded path-width if and only if the corresponding set of line graphs has bounded clique-width or bounded linear clique-width, respectively. This relationship implies some interesting algorithmic properties and re-proves already known results in a very simple way. It also shows that the minimization problem for NLC-width is NP-complete. [Copyright &y& Elsevier]

Abstract: We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469–478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411–417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph , the edge set E can be partitioned into four subsets in such a way that , for , is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G. [Copyright &y& Elsevier]

Abstract: In this paper we introduce the graph layout parameter neighbourhood-width as a variation of the well-known cut-width. The cut-width of a graph is the smallest integer k, such that there is a linear layout , such that for every there are at most k edges with and . The neighbourhood-width of a graph is the smallest integer k, such that there is a linear layout , such that for every the vertices u with can be divided into at most k subsets each members having the same neighbourhood with respect to the vertices with . We show that the neighbourhood-width of a graph differs from its linear clique-width or linear NLC-width at most by one. This relation is used to show that the minimization problem for neighbourhood-width is NP-complete. Furthermore, we prove that simple modifications of neighbourhood-width imply equivalent layout characterizations for linear clique-width and linear NLC-width. We also show that every graph of path-width k or cut-width k has neighbourhood-width at most and we give several conditions such that graphs of bounded neighbourhood-width have bounded path-width or bounded cut-width. [Copyright &y& Elsevier]

Abstract: A spanning subgraph of a connected graph is an -spanner if for any pair of vertices u and v, where and are the usual distance functions in G and S, respectively. The parameter c is called the delay of the spanner. We study edge-disjoint spanners in graphs, focusing on graphs formed as Cartesian products. Our approach is to construct sets of edge-disjoint spanners in a product based on sets of edge-disjoint spanners and colorings of the component graphs. We present several results on general products and then narrow our focus to hypercubes. [Copyright &y& Elsevier]

Abstract: A set of vertices of the graph is called -reducible if the following is true: is -choosable if and only if is -choosable. A -reduced subgraph of is a subgraph of such that contains no -reducible set of some specific forms. In this paper, we show that a 3-reduced subgraph of a non-3-choosable plane graph contains either adjacent 5-faces, or an adjacent 4-face and -face, where . Using this result, we obtain some sufficient conditions for a plane graph to be 3-choosable. In particular, if is of girth 4 and contains no 5- and 6-cycles, then is 3-choosable. [Copyright &y& Elsevier]

Abstract: We give a short proof for the Mixed Connectivity Certificate Theorem of Even, Itkis and Rajsbaum and provide an upper bound on the edge number of a certificate of local -mixed connectivity up to . [Copyright &y& Elsevier]

Abstract: For a graph property , we define a -matching as a set M of disjoint edges such that the subgraph induced by the vertices incident to M has property . Previous examples include strong/induced matchings and uniquely restricted matchings. We explore the general properties of -matchings, but especially the cases where is the property of being acyclic or the property of being disconnected. We consider bounds on and the complexity of the maximum cardinality of a -matching and the minimum cardinality of a maximal -matching. [Copyright &y& Elsevier]

Abstract: A colouring of a strongly regular graph is an allocation of colours (or treatments) to the vertices of the graph. Such a colouring is balanced if every pair of distinct colours occurs equally often on the ends of an edge. When the graph is the complete regular multipartite graph a balanced colouring is just a balanced incomplete-block design, or 2-design. Some constructions are given. For example, colourings of the triangular graph give balanced designs for experiments where the experimental units are unordered pairs of people. An analogue of Fisher''s inequality is proved. In this context, strongly regular graphs may be generalized to arbitrary association schemes. When the association scheme is a collection of circular blocks then a colouring is balanced if the design in blocks is a 2-design and there is undirectional neighbour balance at all distances around the circle. [Copyright &y& Elsevier]

Abstract: We prove that, with one exception, each -graph G that is embeddable in its complement has a self-complementary supergraph of order n. [Copyright &y& Elsevier]

Abstract: Let , a and b be integers with . A graph is called -free if it contains no as an induced subgraph. We prove that every -free G has an -factor if its minimum degree is at leastThis degree condition is sharp. [Copyright &y& Elsevier]

Abstract: It is known that each conjugacy class of actions of on can be represented by a coset diagram where and q is a power of a prime p. In this paper, we are interested in parametrizing the conjugacy classes of actions of the infinite triangle group on For each we then associate a coset diagram depicting the conjugacy class of actions of on We have obtained conditions on and q which guarantee only those coset diagrams which depict homomorphic images of in We are interested in finding also when the coset diagrams for the actions of on contain vertices on the vertical line of symmetry. It will enable us to show that for infinitely many values of the group has minimal genus, while also for infinitely many the group is an -group. [Copyright &y& Elsevier]

Abstract: It is shown that the ratio between separation and rigidity indices of graphs may be arbitrarily large. Paley graphs are such examples. [Copyright &y& Elsevier]

Abstract: An n-tournament is an orientation of a complete n-partite graph. It was proved by J.A. Bondy in 1976 that every strong n-partite tournament has an n-cycle. We characterize strong n-partite tournaments in which a longest cycle is of length n and, thus, settle a problem in Volkmann (Discrete Math. 199 (1999) 279). [Copyright &y& Elsevier]

Let G be a graph and let T be a tree with the same vertex set. Let e be an edge of T and Ae and Be be the vertex sets of the components of T obtained after removal of e. Let EG(Ae,Be) be the set of edges of G with one endvertex in Ae and one endvertex in Be. LetThe paper is devoted to minimization of ec(G:T)• Over all trees with the same vertex set as G.• Over all spanning trees of G.These problems can be regarded as “congestion” problems. [Copyright &y& Elsevier]

Let G be a simple graph and let &Gmacr; denote its complement. We say that G is integral, if its spectrum consists of integral values. In this work we establish a characterization of integral graphs which belong to the class αKa∪βKb,b, where mG denotes the m-fold union of the graph G. [Copyright &y& Elsevier]

Let m1,m2,…,mk be positive integers not less than 3 and let n=∑i=1k mi. Then, it is proved that the complete graph of order 2n+1 can be cyclically decomposed into k(2n+1) cycles such that, for each i=1,2,…,k, the cycle of length mi occurs exactly 2n+1 times. [Copyright &y& Elsevier]

Tura´n's theorem (Mat. Fiz. Lapok 48 (1941) 436) (or rather its extension by Zykov (Mat. Sbornik 24 (66) (1949) 163) answers the following question: For k=2,…,r, what is the maximum number of k-cliques (i.e., subgraphs on k vertices) in a finite graph G, given the clique number r and the number of vertices of G? Here we address—and answer—the following closely related question: For k=3,…,r, what is the maximum number of k-cliques in G, given the clique number r and the number of edges of G? We also prove a “stability theorem” which shows that our result is best possible in a strong sense. [Copyright &y& Elsevier]

In this paper, we consider the number of spanning trees in circulant graphs. For any class of odd valent circulant graphs C2n(a1,a2,…,ak−1,n), where a1,a2,…,ak−1 are fixed jumps and n varies, some formulas, asymptotic behaviors and linear recurrence relations for the number of its spanning trees are obtained, and some known results on the ones in even valent circulant graphs Cn(a1,a2,…,ak) are improved. [Copyright &y& Elsevier]

This paper studies the relaxed game chromatic number of trees and outerplanar graphs. It is proved that if G is a tree then χgd(G)⩽2 for d⩾2. If G is an outerplanar graph, then χgd(G)⩽5 for d⩾2, and χgd(G)⩾3 for d⩽4. [Copyright &y& Elsevier]

The eigenvalues of a graph are the eigenvalues of its adjacency matrix. This paper presents some upper and lower bounds on the greatest eigenvalue and a lower bound on the smallest eigenvalue. [Copyright &y& Elsevier]

A graph is (t,r)-regular iff it has at least one independent t-set of vertices and the open neighborhood of any such set contains exactly r vertices. Our goal is to show that when t⩾3 and the order is sufficiently large, then the structure of (t,r)-regular graphs is similar to, but not exactly the same as the structure of (2,r)-regular graphs as derived by Faudree and Knisley. That is, there is an “almost” complete kernel of order at most r surrounded by satellite cliques, all of the same order, which are “mostly” joined to the kernel. [Copyright &y& Elsevier]

In this paper, we study self-dual codes over GF(p) where p=11,13,17,19,23 and 29. A classification of such codes for small lengths is given. The largest minimum weights of these codes are investigated. Many maximum distance separable self-dual codes are constructed. [Copyright &y& Elsevier]

In this survey article we discuss the existence of quasi-3 designs, and settle the existence question for all v<144. The only such designs are the ones already known. We also consider the question of whether the dual design of a quasi-3 design is a quasi-3 design. [Copyright &y& Elsevier]

Abstract: A vertex of a graph is a boundary vertex if there exists a vertex such that the distance in from to is at least the distance from to any neighbour of . We give the best possible lower bound, up to a constant factor, on the number of boundary vertices of a graph in terms of its minimum degree (or maximum degree). This settles a problem introduced by Hasegawa and Saito. [Copyright &y& Elsevier]

Abstract: We investigate the following question proposed by Erdős: Is there a constant c such that, for each n, if G is a graph with n vertices, edges, and , then G contains an induced proper subgraph H with at least cn vertices and Previously we showed that there exists no such constant by constructing a family of graphs whose induced proper subgraph with minimum degree 3 contains at most vertices. In this paper we present a construction of a family of graphs whose largest induced proper subgraph with minimum degree 3 is . Also a similar construction of a graph with vertices and edges is given. [Copyright &y& Elsevier]