책 이미지
책 정보
· 분류 : 외국도서 > 컴퓨터 > 운영체제(OS) > 일반
· ISBN : 9781439813041
· 쪽수 : 536쪽
· 출판일 : 2011-06-06
목차
A BRIEF INTRODUCTION TO GRAPHS AND THEIR PRODUCTS
Graphs
Graphs and Subgraphs
Paths and Cycles
Trees and Forests
Planar Graphs
Automorphisms and Invariants
Automorphisms
Vertex-Transitivity
Graph Invariants
The No-Homomorphism Lemma
Hypercubes and Isometric Subgraphs
Hypercubes are Sparse
Isometric Subgraphs
Median Graphs
Retracts
Graph Products
Three Fundamental Products
Commutativity, Associativity, and Multiple Factors
Projections and Layers
Classification of Products
The Four Standard Graph Products
The Cartesian Product
The Strong Product
The Direct Product
The Lexicographic Product
FACTORIZATION AND CANCELLATION
Cartesian Product
Prime Factor Decompositions
Cartesian Product and Its Group
Transitive Group Action on Products
Cancellation
S-Prime Graphs
Strong Product
Basic Properties and S-Thin Graphs
Cliques and the Extraction of Complete Factors
Unique Prime Factorization for Connected Graphs
Automorphisms
Direct Product
Nonuniqueness of Prime Factorization
R-Thin Graphs
The Cartesian Skeleton
Factoring Connected, Nonbipartite, R-Thin Graphs
Factoring Connected, Nonbipartite Graphs
Automorphisms
Applications to the Strong Product
Cancellation
Cancellation for the Strong Product
Cancellation for the Direct Product
Anti-Automorphisms and Factorials
Graph Exponentiation
Lexicographic Product
Basic Properties
Self-Complementarity and Cancellation Properties
Commutativity
Factorizations and Nonuniqueness
Automorphisms
ISOMETRIC EMBEDDINGS
The Relation Θ and Partial Cubes
Definition and Basic Properties of Θ
Characterizations of Partial Cubes
Cubic Partial Cubes
Scale Embeddings into Hypercubes
Median Graphs
Mulder’s Convex Expansion
Inequalities for Median Graphs and Partial Cubes
Median Graphs as Retracts
A Fixed Cube Theorem
Median Networks in Human Genetics
The Canonical Isometric Embedding
The Embedding and Its Properties
The Relation Θ and the Cartesian Product
Automorphisms of Canonical Embeddings
A Dynamic Location Problem
Hamming Graphs
Graphs with Finite Windex
Quasi-Median Graphs and Generalizations
Graphs with Finite Windex are Quasi-Median Graphs
Isometries in Strong Products and Product Dimensions
Strong Isometric Dimension
Retracts of Strong Products
Other Product Graph Dimensions
Fixed Box Theorems
Gated Subgraphs and Median Functions
A Fixed Box Theorem for Median Function-Closed Graphs
Feder-Tardif’s Fixed Box Theorems
Fixed Points of Several Nonexpansive Mappings
ALGORITHMS
Graph Representation and Algorithms
Time and Space Complexity
Adjacency List
Breadth-First Search
Adjacency Matrix
Recognizing Hypercubes and Partial Cubes
Hypercubes
Partial Cubes
Efficient Computation of Θ*
Recognizing Partial Cubes in Quadratic Time
Chemical Graphs and the Wiener Index
Benzenoid Graphs as Partial Cubes
The Wiener Index of Benzenoid Graphs in Linear Time
The Wiener Index via the Canonical Isometric Embedding
Arboricity, Squares, and Triangles
Arboricity
Listing Squares and Triangles
Recognizing Median Graphs
A Simple Algorithm
A Fast Algorithm
Triangle-Free Graphs and Median Graphs
Recognizing Partial Hamming Graphs and Quasi-Median Graphs
Hamming Graphs and Partial Hamming Graphs
Quasi-Median Graphs
Computing the Windex
Factoring the Cartesian Product
Product Relation
A Simple Algorithm
Coordinatization
Factorization in O(m log n) Time
Factorization in Linear Time and Space
Recognizing Direct, Strong, and Lexicographic Products
Direct Product
Strong Product
Factoring Thin Graphs
Factoring Non-Thin Graphs
Lexicographic Product
INVARIANTS
Connectivity
Cartesian Product
Critically Connected Graphs and the Lexicographic Product
Strong and Direct Products
Coloring and Hedetniemi’s Conjecture
Product Coloring
Bounds and Three Applications
Fractional and Circular Chromatic Number
Hedetniemi’s Conjecture
Hedetniemi’s Conjecture for 4-Chromatic Graphs
Circular and Fractional Version of Hedetniemi’s Conjecture
Independence Number and Shannon Capacity
Shannon Capacity
Independence in Direct Products
Independence in Cartesian Products
Domination and Vizing’s Conjecture
Vizing’s Conjecture
Clark and Suen’s Approach
Fractional Version of Vizing’s Conjecture
Domination in Direct Products
Cycle Spaces and Bases
The Cycle Space of a Graph
Minimum Cycle Bases for Cartesian and Strong Products
Minimum Cycle Bases for the Lexicographic Product
Minimum Cycle Bases for the Direct Product
Selected Results
One-Factorization and Edge-Coloring
Hamilton Cycles and Hamiltonian Decompositions
Clique Minors in Cartesian Products
Reconstruction, Topological Embeddings, and Flows
Modeling Complex Networks
RELATED CONCEPTS
Infinite Graphs
Growth Rate and Ends
Free Product
Transitive Median Graphs with Finite Blocks
Two-Ended Median Graphs
Cartesian Product
Strong and Direct Product
Lexicographic Product
Products of Digraphs
Definitions
Connectedness
Tournaments and the Lexicographic Product
Prime Factorings
Cancellation
Near Products
Graph Bundles
Approximate Graph Products
Graph Spectra
Zig-Zag Product
Appendix: Hints and Solutions to Exercises
Bibliography
Author Index
Subject Index
Symbol Index
