On Perfect k-Matchings

In this paper, we generalize the notions of perfect matchings, perfect 2-matchings to perfect k-matchings and give a necessary and sufficient condition for the existence of perfect k-matchings. We show that a bipartite graph G contains a perfect k-matching if and only if it contains a perfect matching. Moreover, for regular graphs, we provide a sufficient condition for the existence of perfect k-matching in terms of the edge connectivity.     

Adjacent vertices on the b-matching polyhedron

Given a graph G = (V,E) and an integer vector $\text{b?}\text{N}{}^{\mathrm{v}}$, a b-matching is a set of edges F?E such that any vertex v?V is incident to at most b_v edges in F. The adjacency on the convex hull of the incidence vectors of the b-matchings is characterized by a very general adjacency criterion, the coloring criter on, which is at least sufficient for all 0–1-polyhedra and which can be checked in the b-matching case by a linear algorithm.     

Extremal double hexagonal chains with respect to k-matchings and k-independent sets

“Double hexagonal chains” can be considered as benzenoids constructed by successive fusions of successive naphthalenes along a zig-zag sequence of triples of edges as appear on opposite sides of each naphthalene unit. In this paper, we discuss the numbers of k-matchings and k-independent sets of double hexagonal chains, as well as Hosoya indices and Merrifield-Simmons indices, and obtain some extremal results: among all the double hexagonal chains with the same number of naphthalene units, (a) the double linear hexagonal chain has minimal k-matching number and maximal k-independent set number and (b) the double zig-zag hexagonal chain has maximal k-matching number and minimal k-independent set number, which are extensions to hexagonal chains [L. Zhang and F. Zhang, Extremal hexagonal chains concerning k-matchings and k-independent sets, J. Math. Chem. 27 (2000) 319-329].     

Maximum information stored in a labeled connected network with minimum edges

Given a set X, we consider the problem of finding a graph G with vertex set X and the minimum number of edges such that for i = 1, . . . , m, the subgraph G _i induced from pattern i is a label connected graph with minimum edges. In the paper, we show that the problem is NP hard and develop a heuristic algorithm to get a fewer number of edges to store patterns.     

Exponentially Many Monochromatic <Emphasis Type="Italic">n</Emphasis>-Matchings in <Emphasis Type="Italic">K</Emphasis><Subscript>3<Emphasis Type="Italic">n</Emphasis>-1</Subscript>

Erdös et al and Gerencsér et al had shown that in any 2-edge-coloring of K _3n-1, there is a n-matching containing edges with the same color(we call such matching monochromatic matching). In this paper we show that for any 2-edge-coloring of K _3n-1 there exists a monochromatic subgraph H of K _3n-1 which contains exponentially many monochromatic n-matchings.     

An interpretation of the Dittert conjecture in terms of semi-matchings

Let G be K_n,n with non-negative edge weights and let U and V be the two colour classes of vertices in G. We define a k-semimatching in G to be a set of k edges such that the edges either have distinct ends in U or distinct ends in V. Semimatchings are to be counted according to the product of the weights on the edges in the semimatching. The Dittert conjecture is a longstanding open problem involving matrix permanents. Here we show that it is equivalent to the following assertion: For a fixed total weight, the number of n-semimatchings in G is maximised by weighting all edges of G equally. We also introduce sub-Dittert functions which count k-semimatchings and are analogous to the subpermanent functions which count k-matchings. We prove some results about the extremal values of our sub-Dittert functions, and also that the Dittert conjecture cannot be disproved by means of unweighted graphs.     

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Minimal 2-matching-covered graphs

A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle. A graph G is said to be 2-matching-covered if every edge of G lies in some perfect 2-matching of G. A 2-matching-covered graph is equivalent to a “regularizable” graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if G−e is not 2-matching-covered for all edges e of G. We use Berge’s theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than K₂ and K₄ is 2 and to prove that a minimal 2-matching-covered graph other than K₄ cannot contain a complete subgraph with at least 4 vertices.     

A characterization of triangle-free tolerance graphs

We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).     

Fractional perfect b-matching polytopes I: General theory

The fractional perfect b-matching polytope of an undirected graph G is the polytope of all assignments of nonnegative real numbers to the edges of G such that the sum of the numbers over all edges incident to any vertex v   is a prescribed nonnegative number _bv$b_v$. General theorems which provide conditions for nonemptiness, give a formula for the dimension, and characterize the vertices, edges and face lattices of such polytopes are obtained. Many of these results are expressed in terms of certain spanning subgraphs of G which are associated with subsets or elements of the polytope. For example, it is shown that an element u of the fractional perfect b-matching polytope of G is a vertex of the polytope if and only if each component of the graph of u either is acyclic or else contains exactly one cycle with that cycle having odd length, where the graph of u is defined to be the spanning subgraph of G whose edges are those at which u is positive.     

Generalised Ramsey numbers for small graphs

The generalised Ramsey number R(G₁, G₂,..., G_k) is defined as the smallest integer n such that, if the edges of K_n, the complete graph on n vertices, are coloured using k colours C₁, C₂,..., C_k, then for some i(1≤i≤k) there is a subgraph G_i of K_n with all of its edges colour C_i. When G₁=G₂=...,G_k=G, we use the more compact notation R_k(G).The generalised Ramsey numbers R_k(G) are investigated for all graphs G having at most four vertices (and no isolates). This extends the work of Chvátal and Harary, who made this investigation in the case k=2.     

Approximating the maximum 3-edge-colorable subgraph problem

We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least of its edges, where γ_o(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/15 of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least 6/7 of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound.For a fixed value of a parameter k≥1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be APX-hard for all k≥2. However, approximation algorithms with approximation ratios tending to 1 as k goes to infinity are also known. At present, the best known performance ratios for the cases k=2 and k=3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k=3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C₅’s are also banned).     

Bounds on Randi? indices

The general Randi? index of a molecular graph G is the sum of [d(u)d(v)]^α over all edges uv∈G, where d(v) denotes the degree of the vertex v in G and α is an arbitrary number. When α=−1/2, it is called the Randi? index. Delorme et al. stated a best possible lower bound on the Randi? index of a triangle-free graph with given minimum degree. Their false proof was pointed out by Liu et al. In this note, we derive some sharp bounds on the general Randi? index which implies their lower bound for triangle-free graphs of order n with maximum degree at most n/4, and also prove it for triangle-free graphs with small minimum degree.     

A generalization of interval edge-colorings of graphs

An edge-coloring of a graph G with colors 1,2,…,t is called an interval (t,1)-coloring if at least one edge of G is colored by i, i=1,2,…,t, and the colors of edges incident to each vertex of G are distinct and form an interval of integers with no more than one gap. In this paper we investigate some properties of interval (t,1)-colorings. We also determine exact values of the least and the greatest possible number of colors in such colorings for some families of graphs.     

How to decrease the diameter of triangle-free graphs

Assume that G is a triangle-free graph. Let be the minimum number of edges one has to add to G to get a graph of diameter at most d which is still triangle-free. It is shown that for connected graphs of order n and of fixed maximum degree. The proof is based on relations of and the clique-cover number of edges of graphs. It is also shown that the maximum value of over (triangle-free) graphs of order n is . The behavior of is different, its maximum value is . We could not decide whether for connected (triangle-free) graphs of order n with a positive ε. Received: October 12, 1997     

A Note on Heterochromatic C 4 in Edge-Colored Triangle-Free Graphs

Let G be an edge-colored graph. A heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d ^c (v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. In this paper, we prove that if G is an edge-colored triangle-free graph of order n ≥?9 and ${d^c(v) \geq \frac{(3-\sqrt{5})n}{2}+1}$ for each vertex v of G, G has a heterochromatic C ₄.     

On the Ramsey multiplicity for stars

In 1929, Ramsey proved a theorem guaranteeing that if G₁,G₂,…,G_k are graphs, then there exists an integer r so that if the edges of K_r are colored in any fashion with k colors a monochromatic G_i in color i exists for some i. Harary and Prins suggested the problem of deciding the minimum number of monochromatic G_i in any such coloring. It is the purpose of this paper to establish this minimum number in the case when G_i are stars for each i.     

Relative length of longest paths and longest cycles in triangle-free graphs

In this paper, we study triangle-free graphs. Let G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ₄(G)?|V(G)|+2. We first show that either for any path P in G there exists a cycle C such that |V_P?V_C|?1, or G is isomorphic to exactly one exception. Using this result, we show that for any set S of at most δ vertices in G there is a cycle C such that S⊆V_C.