Search

Abstract: In this paper we consider the circular edge coloring of four families of Class 2 graphs. For the first two we establish the exact value of the circular chromatic index. For the next two, namely Goldberg and Isaacs snarks we derive an upper bound on this graph invariant. Finally, we consider the computational complexity of some problems related to circular edge coloring. [Copyright &y& Elsevier]

Abstract: General angular momentum recoupling coefficients can be expressed as a summation formula over products of 6- coefficients. Yutsis, Levinson and Vanagas developed graphical techniques for representing the general recoupling coefficient as a cubic graph and they describe a set of reduction rules allowing a stepwise generation of the corresponding summation formula. This paper gives an overview of the state-of-the-art heuristic algorithms, used in the latest version of our GYutsis program, for calculating general recoupling coefficients. By means of an experimental setup we show that, in particular for problems of higher order, this approach yields summation formulae which are at least as good, but are often more concise than those obtained by previous algorithms. We also give a counter-example showing that the widespread convention of reducing girth cycles first does not always lead to a shortest reduction. [Copyright &y& Elsevier]

Abstract: In this paper we consider graphs which have no k vertex-disjoint cycles. For given integers let be the maximum order of a graph G with independence number , which has no k vertex-disjoint cycles. We prove that if or , and in general. We also prove the following results: (1) there exists a constant (depending only on ) such that , (2) there exists a constant (depending only on k) such that , and (3) there exists no absolute constant c such that . [Copyright &y& Elsevier]

Abstract: Let be a hereditary property. Let denote the number of forbidden subgraphs, which are contained in G. A graph G is said to be weakly -saturated, if and the edges of the complement of G can be labelled in such way that for the inequality holds, where and . The minimum possible size of weakly -saturated graphs is denoted by . In this paper we shall investigate some properties of weakly saturated graphs. We provide some estimations for the minimum size of weakly -saturated graphs. [Copyright &y& Elsevier]

Abstract: The shadow independent set (SIS) problem being a new NP-complete problem in algorithmic graph theory was introduced in [J. Franco, J. Goldsmith, J. Schlipf, E. Speckenmeyer, R.P. Swaminathan, An algorithm for the class of pure implicational formulas, Discrete Appl. Math. 96 (1999) 89–106.]. It considers a forest F of (rooted) trees and vertices. Further, a function is given mapping the set of all leaves into the set of all vertices of F. Defining the shadow of a leaf as the subtree rooted at SIS asks for the existence of a set S of leaves exactly one from each tree such that no leaf of S is contained in the shadow of any leaf in S. In [J. Franco, J. Goldsmith, J. Schlipf, E. Speckenmeyer, R.P. Swaminathan, An algorithm for the class of pure implicational formulas, Discrete Appl. Math. 96 (1999) 89–106.] the fixed parameter tractability (FPT) of SIS has been shown by obtaining as an upper bound for its computational complexity. Recently, a new FPT bound for SIS was found in [P. Heusch, S. Porschen, E. Speckenmeyer, Improving a fixed parameter tractability time bound for the shadow problem, J. Comput. System Sci. 67 (2003) 772–788.] by dynamic programming techniques. In the present paper FPT is investigated for several generalizations of SIS. First, is replaced by a binary relation assigning an arbitrary number of vertices to each leaf. Substituting F by a set of directed acyclic graphs yields a second (structural) generalization. We prove FPT bounds for these problems by generalizing the techniques in [P. Heusch, S. Porschen, E. Speckenmeyer, Improving a fixed parameter tractability time bound for the shadow problem, J. Comput. System Sci. 67 (2003) 772–788.], which cannot be achieved adapting the results in [J. Franco, J. Goldsmith, J. Schlipf, E. Speckenmeyer, R.P. Swaminathan, An algorithm for the class of pure implicational formulas, Discrete Appl. Math. 96 (1999) 89–106.]. [Copyright &y& Elsevier]

Abstract: Let be a simple hypergraph and let denote its chromatic polynomial. Two hypergraphs and are chromatic equivalent if . The equivalence class of is denoted by . Let and be two classes of hypergraphs. is said to be chromatically characterized in if for every we have . In this paper we prove that uniform hypertrees and uniform unicyclic hypergraphs are chromatically characterized in the class of linear hypergraphs. [Copyright &y& Elsevier]

Abstract: The k-restricted domination number of a graph G is the smallest integer such that given any subset U of k vertices of G, there exists a dominating set of G of cardinality at most containing U. Hence, the k-restricted domination number of a graph G measures how many vertices are necessary to dominate a graph if an arbitrary set of k vertices must be included in the dominating set. When , the k-restricted domination number is the domination number. For , it is known that for all connected graphs of order n and minimum degree at least 2 (see [M.A. Henning, Restricted domination in graphs, Discrete Math. 254 (2002) 175–189]). In this paper we characterize those graphs of order n which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and . These results extend results due to McCuaig and Shepherd [Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749–762]. [Copyright &y& Elsevier]

Abstract: A set of vertices is -regular if it induces a k-regular subgraph of G such that . Note that a connected graph with more than one edge has a perfect matching if and only if its line graph has a -regular set. In this paper, some spectral results on the adjacency matrix of graphs with -regular sets are presented. Relations between the combinatorial structure of a p-regular graph with a -regular set and the eigenspace corresponding to each eigenvalue are deduced. Finally, additional results on the effects of Seidel switching (with respect to a bipartition induced by S) of regular graphs are also introduced. [Copyright &y& Elsevier]

Abstract: There are known several exact results on the crossing numbers of Cartesian products of cycles with “small” graphs. In this paper we summarise known results and we give the crossing number of the Cartesian product for the specific 5-vertex graph H. [Copyright &y& Elsevier]

Abstract: Some aspects of the cost colouring of hypergraphs are considered in the paper. A generalisation of the well-known Brook''s theorem for a cost colouring of hypergraphs is proved. Moreover, a relation between the minimal cost of a colouring of a hypergraph with a set of costs which produce an arithmetic sequence and a number of edges of this hypergraph is investigated. [Copyright &y& Elsevier]

Abstract: A k-ranking of a graph G is a mapping such that any path with endvertices x and y satisfying and contains a vertex z with . The ranking number of G is the minimum k admitting a k-ranking of G. The on-line ranking number of G is the corresponding on-line invariant; in that case vertices of G are coming one by one so that a partial ranking has to be chosen by considering only the structure of the subgraph of G induced by the present vertices. It is known that . In this paper it is proved that . [Copyright &y& Elsevier]

Abstract: The extremal number denotes the maximum number of edges of a graph of order n containing no complete graph as a minor. In this paper we give the exact value of the extremal number for provided that Indeed we show that this number is the size of the Turán Graph and this graph is the only extremal graph. [Copyright &y& Elsevier]

Abstract: In this paper we consider colorings of graphs avoiding certain patterns on paths. Let be a set of variables and let , be a pattern, that is, any sequence of variables. A finite sequence is said to match a pattern if may be divided into non-empty blocks , such that implies , for all . A coloring of vertices (or edges) of a graph is said to be -free if no path in matches a pattern . The pattern chromatic number is the minimum number of colors used in a -free coloring of . Extending the result of Alon et al. [Non-repetitive colorings of graphs, Random Struct. Alg. 21 (2002) 336–346] we prove that if each variable occurs in a pattern at least times then , where is an absolute constant. The proof is probabilistic and uses the Lovász Local Lemma. We also provide some explicit -free colorings giving stronger estimates for some simple classes of graphs. In particular, for some patterns we show that is absolutely bounded by a constant depending only on , for all trees . [Copyright &y& Elsevier]