An E-graph is constructed by replacing each edge in a core graph G with a copy of a graph H. An important property of E-graphs is that their invariant values can be determined from parameters of the original graphs G and H. We determine chromatic number, clique number, vertex and edge cover numbers, vertex and edge independence numbers, circumference, and girth of E-graphs. A characterization of hamiltonian E-graphs is also given.

No description available.

We study combinatorial optimization problems on graphs in the mean-field model, which assigns independent and identically distributed random weights to the edges of the graph. Specifically, we focus on two generalizations of minimum weight matching on graphs. The first problem of minimum cost edge cover finds application in a computational linguistics problem of semantic projection. The second problem of minimum cost many-to-one matching appears as an intermediate optimization step in the restriction scaffold problem applied to shotgun sequencing of DNA. For the minimum cost edge cover on a complete graph on n vertices, where the edge weights are independent exponentially distributed random variables, we show that the expectation of the minimum cost converges to a constant as n →∞ For the minimum cost many-to-one matching on an n x m complete bipartite graph, scaling m as [ n/α ] for some fixed α > 1, we find the limit of the expected minimum cost as a function of α. For both problems, we show that a belief propagation algorithm converges asymptotically to the optimal solution. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings. Our proofs use the machinery of the objective method and local weak convergence, which are ideas developed by Aldous for proving the ζ(2) limit for the minimum cost bipartite matching. We use belief propagation as a constructive proof technique to supplement the objective method. Recursive distributional equations(RDEs) arise naturally in the objective method approach. In a class of RDEs that arise as extensions of the minimum weight matching and travelling salesman problems, we prove existence and uniqueness of a fixed point distribution, and characterize its domain of attraction.