Operations on Graphs Increasing Some Graph Parameters

Details Operations on Graphs Increasing Some Graph Parameters Operations on Graphs Increasing Some Graph Parameters

2011-09-21

arxiv.org/abs/1109.4622v2

Mathematics

Combinatorics

58 pages

Scientific paper

In this partly expository paper we discuss and describe some of our old and recent results on partial orders on the set (m,n)-graphs (i.e. graphs with n vertices and m edges) and some operations on graphs that are monotone with respect to these partial orders. The partial orders under consideration include those related with some Laplacian characteristics of graphs as well as with some probabilistic characteristics of graphs with randomly deleted edges. Section 2 provides some notions, notation, and simple observations. Section 3 contains some basic facts on the Laplacian polynomial of a graph. Section 4 describes various graph operation and their properties. In Section 5 we introduce some partial orders on the set of (m,n)-graphs related, in particular, with the graph Laplacian and the graph reliability (Laplacian posets and reliability posets}). Section 6 contains some old and recent results on the monotonicity of some graph operations with respect to Laplacian posets. Section 7 and 8 include some old and recent results on the monotonicity of some graph operations with respect to reliability posets and to some other parameters of graphs as well as some open problems. Section 9 contains some generalizations of the described results on weighted graphs. Keywords: graph, graph operations, graph posets, random graphs, decomposable graphs, threshold graphs, weighted graphs, spanning subgraphs, Laplacian polynomial and spectrum, adjacency polynomial and spectrum, graph reliability, trees, forests, Hamiltonian cycle and path, symmetric polynomials

Affiliated with

Also associated with

No associations

Rating

Operations on Graphs Increasing Some Graph Parameters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Operations on Graphs Increasing Some Graph Parameters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Operations on Graphs Increasing Some Graph Parameters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-258197