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: 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: 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: 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: 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: 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: A Fano colouring is a colouring of the edges of a cubic graph by points of the Fano plane such that the colours of any three mutually adjacent edges form a line of the Fano plane. It has recently been shown by Holroyd and Škoviera [Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Ser. B 91 (2004) 57–66] that a cubic graph has a Fano colouring if and only if it is bridgeless. In this paper we prove that six, and conjecture that four, lines of the Fano plane are sufficient to colour any bridgeless cubic graph. We establish connections of our conjecture to other conjectures concerning bridgeless cubic graphs, in particular to the well-known conjecture of Fulkerson about the existence of a double covering by 1-factors in every bridgeless cubic graph. [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]

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]

This paper discusses a method for recognizing certain graph classes based on elimination schemes more efficiently. We reduce the time bound for recognizing quasi-triangulated graphs from O(n3) to O(n2.77), and perfect elimination bipartite and cop-win graphs from O(n3) to O(n3/log n). [Copyright &y& Elsevier]

We investigate the class of graphs defined by the property that every induced subgraph has a vertex which is either simplicial (its neighbours form a clique) or co-simplicial (its non-neighbours form an independent set). In particular we give the list of minimal forbidden subgraphs for the subclass of graphs whose vertex-set can be emptied out by first recursively eliminating simplicial vertices and then recursively eliminating co-simplicial vertices. [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]

The upper bound of the chromatic number of simple graphs is explored. Its original idea comes from Coffman, Hakimi and Schmeichel, who recently studied the chromatic number of graphs with strong conditions. In this paper, corresponding conditions are weakened and the result proves that of Ershov and Kozhukhin' s. [ABSTRACT FROM AUTHOR]