Matchings and walks in graphs

The matching polynomial α(G, x) of a graph G is a form of the generating function for the number of sets of k independent edges of G. in this paper we show that if G is a graph with vertex v then there is a tree T with vertex w such that \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{\alpha (G\backslash v, x)}}{{\alpha (G, x)}} = \frac{{\alpha (T\backslash w, x)}}{{\alpha (T, x)}}. $\end{document} This result has a number of consequences. Here we use it to prove that α(G\v, 1/x)/xα(G, 1/x) is the generating function for a certain class of walks in G. As an application of these results we then establish some new properties of α(G, x).     

A class of planar well-covered graphs with girth four

A well-covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1-well-covered graph was introduced by Staples in her 1975 dissertation: a well-covered graph G is 1-well-covered if and only if G - v is also well covered for every point v in G. Except for K₂ and C₅, every 1-well-covered graph contains triangles or 4-cycles. We show that all planar 1-well-covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family. © 1995 John Wiley & Sons, Inc.     

On some subclasses of well-covered graphs

A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well-covered graphs are classified by the W_n property: For a positive integer n, a graph G belongs to class W_n if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of W_n graphs containing arbitrarily large independent sets. A characterization of W_n graphs in terms of well-covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in W_n graphs.     

On anti-magic labeling for graph products

An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K₂ are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p-vertex graphs with minimum degree Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products.     

Domination-balanced graphs

A set D of vertices in a graph is said to be a dominating set if every vertex not in D is adjacent to some vertex in D. The domination number β(G) of a graph G is the size of a smallest dominating set. G is called domination balanced if its vertex set can be partitioned into β(G) subsets so that each subset is a smallest dominating set of the complement G of G. The purpose of this paper is to characterize these graphs.     

On antimagic directed graphs

An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In (N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990, pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than K₂, is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected d‐regular graph admits an orientation which is antimagic. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 219–232, 2010     

Super Edge-connectivity and Zeroth-order General Randić Index for −1 ≤ <Emphasis Type="Italic">α</Emphasis> &lt; 0

Let G be a connected graph with order n, minimum degree δ = δ(G) and edge-connectivity λ = λ(G). A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randi? index \(R_\alpha ^0\left( G \right) = \sum\limits_{x \in V\left( G \right)} {d_G^\alpha \left( x \right)} \), where d_G(x) denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randi? index for ?1 ≤ α < 0, respectively.     

On conservative and supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. A graph G is called conservative if it admits an orientation and a labelling of the edges by integers {1,…,|E(G)|} such that at each vertex the sum of the labels on the incoming edges is equal to the sum of the labels on the outgoing edges. In this paper we deal with conservative graphs and their connection with the supermagic graphs. We introduce a new method to construct supermagic graphs using conservative graphs. Inter alia we show that the union of some circulant graphs and regular complete multipartite graphs are supermagic.     

Survey of Double Vertex Graphs

 Let G be a (V,E) graph of order p≥2. The double vertex graph U ₂ (G) is the graph whose vertex set consists of all 2-subsets of V such that two distinct vertices {x,y} and {u,v} are adjacent if and only if |{x,y}∩{u,v}|=1 and if x=u, then y and v are adjacent in G. For this class of graphs we discuss the regularity, eulerian, hamiltonian, and bipartite properties of these graphs. A generalization of this concept is n-tuple vertex graphs, defined in a manner similar to double vertex graphs. We also review several recent results for n-tuple vertex graphs. Received: October, 2001 Final version received: September 20, 2002 Dedicated to Frank Harary on the occasion of his Eightieth Birthday and the Manila International Conference held in his honor     

Total Rainbow Connection Number and Complementary Graph

A vertex-colored graph G is rainbow vertex connected if any two distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex connected. In this paper, we prove that for a connected graph G, if \({{\rm diam}(\overline{G}) \geq 3}\), then \({{\rm rvc}(G) \leq 2}\), and this bound is tight. Next, we obtain that for a triangle-free graph \({\overline{G}}\) with \({{\rm diam}(\overline{G}) = 2}\), if G is connected, then \({{\rm rvc}(G) \leq 2}\), and this bound is tight. A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we prove that for a triangle-free graph \({\overline{G}}\) with \({{\rm diam}(\overline{G}) = 3}\), if G is connected, then trc\({(G) \leq 5}\), and this bound is tight. Next, a Nordhaus–Gaddum-type result for the total rainbow connection number is provided. We show that if G and \({\overline{G}}\) are both connected, then \({6 \leq {\rm trc} (G) + {\rm trc}(\overline{G}) \leq 4n - 6.}\) Examples are given to show that the lower bound is tight for \({n \geq 7}\) and n = 5. Tight lower bounds are also given for n = 4, 6.     

The Ulam number of infinite graphs

The following is a conjecture of Ulam: In any partition of the integer lattice on the plane into uniformly bounded sets, there exists a set that is adjacent to at least six other sets. Two sets are adjacent if each contain a vertex of the same unit square. This problem is generalized as follows. Given any uniformly bounded partitionP of the vertex set of an infinite graphG with finite maximum degree, letP (G) denote the graph obtained by letting each set of the partition be a vertex ofP (G) where two vertices ofP (G) are adjacent if and only if the corresponding sets have an edge between them. The Ulam number ofG is defined as the minimum of the maximum degree ofP (G) where the minimum is taken over all uniformly bounded partitionsP. We have characterized the graphs with Ulam number 0, 1, and 2. Restricting the partitions of the vertex set to connected subsets, we obtain the connected Ulam number ofG. We have evaluated the connected Ulam numbers for several infinite graphs. For instance we have shown that the connected Ulam number is 4 ifG is an infinite grid graph. We have settled the Ulam conjecture for the connected case by proving that the connected Ulam number is 6 for an infinite triangular grid graph. The general Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6. We also describe some interesting geometric consequences of the Ulam number, mainly concerning good drawings of infinite graphs.     

Connected Domatic Number in Planar Graphs

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.     

The Rainbow Vertex-disconnection in Graphs

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.     

Antimagic Labelings of Join Graphs

An antimagic labeling of a graph with q edges is a bijection from the set of edges of the graph to the set of positive integers \({\{1, 2,\dots,q\}}\) such that all vertex weights are pairwise distinct, where a vertex weight is the sum of labels of all edges incident with the vertex. The join graph G + H of the graphs G and H is the graph with \({V(G + H) = V(G) \cup V(H)}\) and \({E(G + H) = E(G) \cup E(H) \cup \{uv : u \in V(G) {\rm and} v \in V(H)\}}\). The complete bipartite graph K _m,n is an example of join graphs and we give an antimagic labeling for \({K_{m,n}, n \geq 2m + 1}\). In this paper we also provide constructions of antimagic labelings of some complete multipartite graphs.     

Global cycle properties in graphs with large minimum clustering coefficient

Let 𝒫 be a graph property. A graph G is said to be locally 𝒫 (closed locally 𝒫) if the subgraph induced by the open neighbourhood (closed neighbourhood, respectively) of every vertex in G has property 𝒫. The clustering coefficient of a vertex is the proportion of pairs of its neighbours that are themselves neighbours. The minimum clustering coefficient of G is the smallest clustering coefficient among all vertices of G. Let H be a subgraph of a graph G and let S ? V (H). We say that H is a strongly induced subgraph of G with attachment set S, if H is an induced subgraph of G and the vertices of V (H) ? S are not incident with edges that are not in H. A graph G is fully cycle extendable if every vertex of G lies in a triangle and for every nonhamiltonian cycle C of G, there is a cycle of length |V (C)|?+?1 that contains the vertices of C. A complete characterization, of those locally connected graphs with minimum clustering coefficient 1/2 and maximum degree at most 6 that are fully cycle extendable, is given in terms of forbidden strongly induced subgraphs (with specified attachment sets). Moreover, it is shown that all locally connected graphs with Δ?≤?6 and sufficiently large minimum clustering coefficient are weakly pancylic, thereby proving Ryj´ǎcek’s conjecture for this class of graphs.     

Antimagic labeling of generalized pyramid graphs

An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Even graphs

A nontrivial connected graph G is called even if for each vertex v of G there is a unique vertex v such that d(v, v ) = diam G. Special classes of even graphs are defined and compared to each other. In particular, an even graph G is called symmetric if d(u, v) + d(u, v ) = diam G for all u, v ∈ V(G). Several properties of even and symmetric even graphs are stated. For an even graph of order n and diameter d other than an even cycle it is shown that n ≥ 3d – 1 and conjectured that n ≥ 4d – 4. This conjecture is proved for symmetric even graphs and it is shown that for each pair of integers n, d with n even, d ≥ 2 and n ≥ 4d – 4 there exists an even graph of order n and diameter d. Several ways of constructing new even graphs from known ones are presented.     

The eavesdropping number of a graph

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.     

On randomized greedy matchings

We analyze a randomized greedy matching algorithm (RGA) aimed at producing a matching with a large number of edges in a given weighted graph. RGA was first introduced and studied by Dyer and Frieze in [3] for unweighted graphs. In the weighted version, at each step a new edge is chosen from the remaining graph with probability proportional to its weight, and is added to the matching. The two vertices of the chosen edge are removed, and the step is repeated until there are no edges in the remaining graph. We analyze the expected size μ(G) of the number of edges in the output matching produced by RGA, when RGA is repeatedly applied to the same graph G. Let r(G)=μ(G)/m(G), where m(G) is the maximum number of edges in a matching in G. For a class 𝒢 of graphs, let ρ(𝒢) be the infimum values r(G) over all graphs G in 𝒢 (i.e., ρ is the “worst” performance ratio of RGA restricted to the class 𝒢). Our main results are bound for μ, r, and ρ. For example, the following results improve or generalize similar results obtained in [3] for the unweighted version of RGA; \begin{eqnarray*}r(G)&\ge&{1\over 2-|V|/2|E|}\quad \mbox{(if $G$ has a perfect matching)}\\ {\sqrt{26}-4\over 2}&\le&\rho(\hbox{\sf SIMPLE PLANAR GRAPHS})\le.68436349\\ \rho(\hbox{SIMPLE $\Delta$-GRAPHS})&\ge&{1\over2}+{\sqrt{(\Delta-1)^2+1}-(\Delta-1)\over2}\end{eqnarray*} (where the class is the set of graphs of maximum degree at most Δ). © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 : 353–383, 1997