Forcing matchings on square grids

Let G be a graph that admits a perfect matching. The forcing number of a perfect matching M of G is defined as the smallest number of edges in a subset S M, such that S is in no other perfect matching. We show that for the 2n × 2n square grid, the forcing number of any perfect matching is bounded below by n and above by n². Both bounds are sharp. We also establish a connection between the forcing problem and the minimum feedback set problem. Finally, we present some conjectures about forcing numbers in other graphs.     

Primitive graphs with given exponents and minimum number of edges

A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even.     

Hamiltonian cycles in n-factor-critical graphs

A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with , then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with , then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2.     

Pancyclicity mod k of claw-free graphs and K1,4-free graphs

For any natural number k, a graph G is said to be pancyclic mod k if it contains a cycle of every length modulo k. In this paper, we show that every K_1,4-free graph G with minimum degree δ(G)k+3 is pancyclic mod k and every claw-free graph G with δ(G)k+1 is pancyclic mod k, which confirms Thomassen's conjecture (J. Graph Theory 7 (1983) 261–271) for claw-free graphs.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

Cycle-saturated graphs of minimum size

A graph G is called C_k-saturated if G contains no cycles of length k but does contain such a cycle after the addition of any new edge. Bounds are obtained for the minimum number of edges in C_k-saturated graphs for all k ≠ 8 or 10 and n sufficiently large. In general, it is shown that the minimum is between n + c₁n/k and n + c₂n/k for some positive constants c₁ and C₂. Our results provide an asymptotic solution to a 15-year-old problem of Bollobás.     

Vertex pancyclic graphs

Let G be a graph of order n. A graph G is called pancyclic if it contains a cycle of length k for every 3kn, and it is called vertex pancyclic if every vertex is contained in a cycle of length k for every 3kn. In this paper, we shall present different sufficient conditions for graphs to be vertex pancyclic.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

On the Differential Polynomial of a Graph

We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial B(G; x) :=∑?(G)k=-nB_k(G) x~(n+k), where B_k(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G;x) and its coefficients.In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G.     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

Graphs with no M-alternating path between two vertices

Let G be a graph with a perfect matching M. In this paper, we prove two theorems to characterize the graph G in which there is no M-alternating path between two vertices x and y in G.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

Independent sets and repeated degrees

We answer a question of Erdös, Faudree, Reid, Schelp and Staton by showing that for every integer k 2 there is a triangle-free graph G of order n such that no degree in G is repeated more than k times and ind(G) = (1 + o(1))n/k.     

Zagreb indices of graphs

The first Zagreb index M₁(G) is equal to the sum of squares of the degrees of the vertices, and the second Zagreb index M₂(G) is equal to the sum of the products of the degrees of pairs of adjacent vertices of the underlying molecular graph G. In this paper, we obtain lower and upper bounds on the first Zagreb index M₁(G) of G in terms of the number of vertices (n), number of edges (m), maximum vertex degree (Δ), and minimum vertex degree (δ). Using this result, we find lower and upper bounds on M₂(G). Also, we present lower and upper bounds on M₂(G) +M₂(G) in terms of n, m, Δ, and δ, where G denotes the complement of G. Moreover, we determine the bounds on first Zagreb coindex M₁(G) and second Zagreb coindex M₂(G). Finally, we give a relation between the first Zagreb index and the second Zagreb index of graph G.     

Algorithms for finding a Kth best valued assignment

We consider a new problem, the Kth best valued assignment problem. Given a bipartite graph G and a cost vector w on its edge set, this is the problem of finding a perfect matching M_k in G such that there exist perfect matchings M₁,…,M_K−1 satisfying w(M₁) < < w(M_K−1) < w(M_K), and w(M_K) < w(M) for all perfect matchings M with w(M) ≠ w(M₁),…,w(M_K). Here w(M) denotes the sum of costs of edges in M. In this paper, we propose two algorithms for solving this problem and verify the efficiency of our algorithms by our preliminary computational experiments.     

Bipartite dimensions and bipartite degrees of graphs

A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G'sbipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d(G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d(K_n) = [log₂n], η(K_n) = d(K_n) for n 16, and η(K_n) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices.     

Covering a graph by complete bipartite graphs

We prove the following theorem: the edge set of every graph G on n vertices can be partitioned into the disjoint union of complete bipartite graphs such that each vertex is contained by at most c(n/log n) of the bipartite graphs.     

No-hole L(2,1)-colorings

An L(2,1)-coloring of a graph G is a coloring of G's vertices with integers in {0,1,…,k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ(G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ(G), and the hole index ρ(G) of G is the minimum number of colors in {0,1,…,λ(G)} not used in a span coloring. We say that G is full-colorable if ρ(G)=0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span μ(G) of G as ∞ if G has no no-hole coloring; otherwise μ(G) is the minimum k for which G has a no-hole coloring using colors in {0,1,…,k}.

Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ3 are full-colorable, all graphs G with n=λ(G)+1 are full-colorable, μ(G)λ(G)+ρ(G) if G is not full-colorable and nλ(G)+2, and G has a no-hole coloring if and only if nλ(G)+1. We prove two extremal results for colorings. First, for every m1 there is a G with ρ(G)=m and μ(G)=λ(G)+m. Second, for every m2 there is a connected G with λ(G)=2m, n=λ(G)+2 and ρ(G)=m.     

A Note on Strong Edge Coloring of Sparse Graphs

A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ'_s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2 k. Yang and Zhu [J. Graph Theory, 83, 334–339(2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4 kΔ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤ 4 kΔ-2 k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most(4 k-1)Δ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤(4 k-1)Δ-2 k + 1.     

On total covers of graphs

A total cover of a graph G is a subset of V(G)E(G) which covers all elements of V(G)E(G). The total covering number ₂(G) of a graph G is the minimum cardinality of a total cover in G. In [1], it is proven that ₂(G)[n/2] for a connected graph G of order n. Here we consider the extremal case and give some properties of connected graphs which have a total covering number [n/2]. We prove that such a graph with even order has a 1-factor and such a graph with odd order is factor-critical.