赋权图的w密度和w平衡性

The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it. In this paper,a good characterization of w-balanced weighted graphs is given. Applying this characterization ,many large w-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed. It is shown that the w-density theory is closely related to the study of SEW(G,w) games.     

Graph colourings with forbidden k-coloured subgraphs

Abstract

For a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G.     

Well-covered graphs and factors

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has a perfect [1,2]-factor F_G, i.e. a spanning subgraph such that each component is 1-regular or 2-regular. Here, we characterize all well-covered graphs G satisfying α(G)=α(F_G) for some perfect [1,2]-factor F_G. This class contains all well-covered graphs G without isolated vertices of order n with α?(n-1)/2, and in particular all very well-covered graphs.     

Induced Decompositions of Graphs

We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.     

Saturated graphs with minimal number of edges

Let F = {F₁,…} be a given class of forbidden graphs. A graph G is called F-saturated if no F_i ∈ F is a subgraph of G but the addition of an arbitrary new edge gives a forbidden subgraph. In this paper the minimal number of edges in F-saturated graphs is examined. General estimations are given and the structure of minimal graphs is described for some special forbidden graphs (stars, paths, m pairwise disjoint edges).     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

A characterization of chain probe graphs

A chain probe graph is a graph that admits an independent set S of vertices and a set F of pairs of elements of S such that G+F is a chain graph (i.e., a 2K ₂-free bipartite graph). We show that chain probe graphs are exactly the bipartite graphs that do not contain as an induced subgraph a member of a family of six forbidden subgraphs, and deduce an O(n ²) recognition algorithm.     

Hereditary Efficiently Dominatable Graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. We introduce graphs that are hereditary efficiently dominatable in that sense that every induced subgraph of the graph contains an efficient dominating set. We prove a decomposition theorem for (bull, fork, C₄)‐free graphs, based on which we characterize, in terms of forbidden induced subgraphs, the class of hereditary efficiently dominatable graphs. We also give a decomposition theorem for hereditary efficiently dominatable graphs and examine some algorithmic aspects of such graphs. In particular, we give a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs by reducing the problem to the maximum weight independent set problem in claw‐free graphs.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

On first-order definitions of subgraph isomorphism properties

Let φ(F) be the property of containing (as a subgraph) an isomorphic copy of a graph F. It is easy to show that this property cannot be defined in a first-order language by a sentence with a quantifier depth (or variable width) strictly less than the number of vertices in F. Nevertheless, such a definition exists in some classes of graphs. Three classes of graphs are considered: connected graphs with a large number of vertices, graphs with large treewidth, and graphs with high connectivity.     

Colourings of the cartesian product of graphs and multiplicative Sidon sets

Let F be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph G with no bichromatic subgraph in F is F-free. The F-free chromatic number χ(G,F) of a graph G is the minimum number of colours in an F-free colouring of G. For appropriate choices of F, several well-known types of colourings fit into this framework, including acyclic colourings, star colourings, and distance-2 colourings. This paper studies F-free colourings of the cartesian product of graphs.     

Supereulerian graphs: A survey

A graph is supereulerian if it has a spanning eulerian subgraph. There is a rduction method to determine whether a graph is supereulerian, and it can also be applied to study other concepts, e.g., hamiltonian line graphs, a certain type of double cycle cover, and the total interval number of a graph. We outline the research on supereulerian graphs, the reduction method, and its applications.     

Progress on perfect graphs

 A graph is perfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect graphs is important for several reasons. For instance, many problems of interest in practice but intractable in general can be solved efficiently when restricted to the class of perfect graphs. Also, the question of when a certain class of linear programs always have an integer solution can be answered in terms of perfection of an associated graph. In the first part of the paper we survey the main aspects of perfect graphs and their relevance. In the second part we outline our recent proof of the Strong Perfect Graph Conjecture of Berge from 1961, the following: a graph is perfect if and only if it has no induced subgraph isomorphic to an odd cycle of length at least five, or the complement of such an odd cycle. Received: December 19, 2002 / Accepted: April 29, 2003 Published online: May 28, 2003 Key words. Berge graph – perfect graph – skew partition Mathematics Subject Classification (1991): 05C17     

Graph polynomials from principal pivoting

The recursive computation of the interlace polynomial introduced by Arratia, Bollobás and Sorkin is defined in terms of a new pivoting operation on undirected simple graphs. In this paper, we interpret the new pivoting operation on graphs in terms of standard pivoting (on matrices). Specifically, we show that, up to swapping vertex labels, Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivot transform on the graph's adjacency matrix, provided that all computations are performed in the Galois field F₂. Principal pivoting on adjacency matrices over F₂ has a natural counterpart on isotropic systems. Thus, our view of the interlace polynomial is closely related to the one by Aigner and van der Holst.The observations that adjacency matrices of undirected simple graphs are skew-symmetric in F₂ and that principal pivoting preserves skew-symmetry in all fields suggest to extend Arratia et al.'s pivoting operation to fields other than F₂. Thus, the interlace polynomial extends to polynomials on gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry non-zero weights that differ only by their sign. Extending a proof by Aigner and van der Holst, we show that the extended interlace polynomial can be represented in a non-recursive form analogous to the non-recursive form of the original interlace polynomial, i.e., the Martin polynomial.For infinite fields it is shown that the extended interlace polynomial does not depend on the (non-zero) gains, as long as they obey a non-singularity condition. These gain graphs are all supported by a single undirected simple graph. Thus, a new graph polynomial is defined for undirected simple graphs. The recursive computation of the new polynomial can be done such that all ends of the recursion correspond to independent sets. Moreover, its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.     

A Construction of Uniquely C4-free colourable Graphs

Abstract

An F-free colouring of a graph G is a partition {V₁,V₂,…,V_n} of the vertex set V(G) of G such that F is not an induced subgraph of G[V_i] for each i. A graph is uniquely F-free colourable if any two .F-free colourings induce the same partition of V(G). We give a constructive proof that uniquely C₄-free colourable graphs exist.     

Balanced group-labeled graphs

A group-labeled graph is a graph whose vertices and edges have been assigned labels from some abelian group. The weight of a subgraph of a group-labeled graph is the sum of the labels of the vertices and edges in the subgraph. A group-labeled graph is said to be balanced if the weight of every cycle in the graph is zero. We give a characterization of balanced group-labeled graphs that generalizes the known characterizations of balanced signed graphs and consistent marked graphs. We count the number of distinct balanced labellings of a graph by a finite abelian group $\Gamma$ and show that this number depends only on the order of $\Gamma$ and not its structure. We show that all balanced labellings of a graph can be obtained from the all-zero labeling using simple operations. Finally, we give a new constructive characterization of consistent marked graphs and markable graphs, that is, graphs that have a consistent marking with at least one negative vertex.     

The independence number of HH-homogeneous graphs and a classification of MB-homogeneous graphs

We show that the independence number of a countably infinite connected HH-homogeneous graph that does not contain the Rado graph as a spanning subgraph is finite and present a classification of MB-homogeneous graphs up to bimorphism-equivalence as a consequence.     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.     

Size and independence in triangle-free graphs with maximum degree three

Let C be the class of triangle-free graphs with maximum degree at most three. A lower bound for the number of edges in a graph of C is derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As corollaries, we obtain the best possible lower bound for the independence ratio of a graph in C and evaluate some Ramsey-type numbers.