Maximum induced matchings in graphs

We provide a formula for the number of edges of a maximum induced matching in a graph. As applications, we give some structural properties of (k + 1)K₂-free graphs, construct all 2K₂-free graphs, and count the number of labeled 2K₂-free connected bipartite graphs.     

Maximum fractional factors in graphs

We prove that fractional k-factors can be transformed among themselves by using a new adjusting operation repeatedly. We introduce, analogous to Berge’s augmenting path method in matching theory, the technique of increasing walk and derive a characterization of maximum fractional k-factors in graphs. As applications of this characterization, several results about connected fractional 1-factors are obtained.     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

图的割宽最大值问题

§ 1　IntroductionThe cutwidth minimization problem for graphs arises from the circuitlayout of VLSIdesigns[1 ] .Chung pointed outthatthe cutwidth often corresponds to the area of the layoutin array layout in VLSI design[2 ] .In the layout models,the cutwidth problem deals withthe number of edges passing over a vertex when all vertices are arranged in a path.For agraph G with vertex set V(G) and edge set E(G) ,a labeling of G is a one-to-one mapping ffrom V(G) to the integers.The cutwid…     

Maximum genus of regular graphs

This paper provides tight lower bounds on the maximum genus of a regular graph in terms of its cycle rank. The main tool is a relatively simple theorem that relates lower bounds with the existence (or non-existence) of induced subgraphs with odd cycle rank that are separated from the rest of the graph by cuts of size at most three. Lower bounds on the maximum genus are obtained by bounding from below the size of these odd subgraphs. As a special case, upper-embeddability of a class of graphs is caused by an absence of such subgraphs. A well-known theorem stating that every 4-edge-connected graph is upper-embeddable is a straightforward corollary of the employed method.     

Maximum bipartite subgraphs in H-free graphs

Czechoslovak Mathematical Journal - Given a graph G, let f(G) denote the maximum number of edges in a bipartite subgraph of G. Given a fixed graph H and a positive integer m, let f(m, H) denote the...     

Maximum bipartite subgraphs of Kneser graphs

We investigate the maximum number of edges in a bipartite subgraph of the Kneser graphK(n, r). The exact solution is given for eitherr arbitrary andn (4.3 + o(1))r, orr = 2 andn arbitrary. The problem is in connection with the study of the bipartite subgraph polytope of a graph.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences     

Maximum chromatic polynomials of 2-connected graphs

In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles C_n and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ C_n} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having _X(G) = 2 and _X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined.     

Maximum induced matching problem on hhd-free graphs

We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m²) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m³). Then, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results.     

Maximum independent sets on random regular graphs

We determine the asymptotics of the independence number of the random d-regular graph for all \({d\geq d_0}\). It is highly concentrated, with constant-order fluctuations around \({n\alpha_*-c_*\log n}\) for explicit constants \({\alpha_*(d)}\) and \({c_*(d)}\). Our proof rigorously confirms the one-step replica symmetry breaking heuristics for this problem, and we believe the techniques will be more broadly applicable to the study of other combinatorial properties of random graphs.     

Clique-critical graphs: Maximum size and recognition

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K^-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.     

Maximum acyclic and fragmented sets in regular graphs

We show that a typical d‐regular graph G of order n does not contain an induced forest with around vertices, when n ? d ? 1, this bound being best possible because of a result of Frieze and ?uczak [6]. We then deduce an affirmative answer to an open question of Edwards and Farr (see [4]) about fragmentability, which concerns large subgraphs with components of bounded size. An alternative, direct answer to the question is also given. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 149–156, 2008     

Maximum vertex and face degree of oblique graphs

Let G=(V,E,F) be a 3-connected simple graph imbedded into a surface S with vertex set V, edge set E and face set F. A face α is an 〈a₁,a₂,…,a_k〉-face if α is a k-gon and the degrees of the vertices incident with α in the cyclic order are a₁,a₂,…,a_k. The lexicographic minimum 〈b₁,b₂,…,b_k〉 such that α is a 〈b₁,b₂,…,b_k〉-face is called the type of α.Let z be an integer. We consider z-oblique graphs, i.e. such graphs that the number of faces of each type is at most z. We show an upper bound for the maximum vertex degree of any z-oblique graph imbedded into a given surface. Moreover, an upper bound for the maximum face degree is presented. We also show that there are only finitely many oblique graphs imbedded into non-orientable surfaces.     

Maximum graphs with a unique k-factor

For suitable integers p and k, let f(p, k) denote the maximum number of edges in a graph of order p which has a unique k-factor. The values of f(p, k) are determined for k = 2, p ? 3, and p ? 2 and the extremal graphs are determined.