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: Bipartite graphs and are bi-placeabe if there is a bijection such that and for every edge ). We prove that if G and H are two bipartite graphs of order such that the sizes of G and H satisfy and , and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that for integers p and such that for and every bipartite balanced graph G of order 2p and size at least contains mutually vertex disjoint cycles , unless . [Copyright &y& Elsevier]

Abstract: We construct multigraphs of any large order with as few as only four 2-decompositions into Hamilton cycles or only two 2-decompositions into Hamilton paths. Nevertheless, some of those multigraphs are proved to have exponentially many Hamilton cycles (Hamilton paths). Two families of large simple graphs are constructed. Members in one class have exactly 16 hamiltonian pairs, in another class exactly four traceable pairs. These graphs also have exponentially many Hamilton cycles and Hamilton paths, respectively. The exact numbers of (Hamilton) cycles and paths are expressed in terms of Fibonacci-like numbers which count 2-independent vertex (or edge) subsets on the n-path. This approach is prompted by the fact that the square of the n-cycle is the starting point of constructions. Presented results complement, improve on, or extend the corresponding well-known Thomason''s results. [Copyright &y& Elsevier]

Abstract: We consider the squares of intersection graphs of hypergraphs and simple graphs. The Berge-type characterization for squares of intersection graphs of hypergraphs is obtained. The analogue of Whitney theorem for squares of intersection graphs of trees is proved. Using the connection between induced matchings of graph and independent sets of square of line graph, new polynomial solvable cases for the weighted induced matching problem are obtained. [Copyright &y& Elsevier]

Abstract: A rough structure theorem for small separations in symmetric graphs is developed. Let be a vertex transitive graph, let be finite with set for some . We show that whenever the diameter of G is at least , either , or G has a (bounded) ring-like structure and A is efficiently contained in an interval. This theorem has applications to the study of product sets and expansion in groups. [Copyright &y& Elsevier]

Abstract: Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollak [R.L Graham, H.Pollak On the addressing problem for loop switching, Bell System Technol. J. 50 (1971) 2495–2519] and Djokovic̀ [D. Djokovic̀, Distance preserving subgraphs of the hypercubes, J. Combin. Theory, Ser B41 (1973), 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, we determine all subdivisions of a given configuration which can be embedded isometrically in the hypercube. More specially, we deal with the case where this configuration is a connected graph of order 4 on one hand and the case where the configuration is a fan on the other hand. Finally, we conjecture that a subdivision of a complete graph of order is a partial cube if and only if this one is isomorphic to or there exists edges of adjacent to a common vertex in the subdivision and the other edges of contain odd added vertices. This proposition is true when the order . [Copyright &y& Elsevier]

Abstract: In this paper we describe how the problem of computing an irregularity strength of a graph may be expressed and solved in terms of constraint programming over finite domains, i.e. CP(FD). We also present some theoretical and experimental results concerning an irregularity strength computed for cubic graphs and graphs. Additionally, we give some remarks on the implementation of our approach in the Oz programming language on the platform of the Mozart system. [Copyright &y& Elsevier]

Abstract: We define a two-terminal directed acyclic graph (st-dag) characterized by a special structure of its mincuts and call it a nested graph. It is proved that every nested graph is series-parallel as well. We show that an st-dag of order n has exactly mincuts if and only if it is nested. [Copyright &y& Elsevier]

Abstract: A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of is less than the total domination number of G. These graphs we call -critical. If such a graph G has total domination number k, we call it k--critical. We verify an open problem of k--critical graphs and obtain some results on the characterization of total domination critical graphs of order . [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]

The article discusses the comments of researcher Steve Borgatti on Doreian Splits. Borgatti is on the mark in suggesting that the author and his colleague researchers look at nested regular equivalences. One suggestion, which is only a suggestion, is that the researchers look for such a nesting by considering regular equivalence as a local property, which is then sequentially expanded as more of the network is taken into account. The structures that Borgatti and the author discuss are really toy models in the sense that they have a simple structure and there are exact regular equivalences that can be found. Empirically, this is unlikely to occur so that exact equivalences, under any definition, will be infrequent. It is not clear to the author what the nested hierarchy would be like when there are no exact regular equivalences in the structure. The Doreian split is an intuitively satisfying response to a specific problem that arises in symmetric graphs plus a fairly large number of non-symmetric gaits.

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]