Introduction to graphs

Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results...

Efficient network design, construction and analysis are important topics, considering the highly dynamic environment in which data communication occurs nowadays. In this paper we address several problems concerning these topics from an algorithmic point of view.

We apply in this article (non rigorous) statistical mechanics methods to the problem of counting long circuits in graphs. The outcomes of this approach have two complementary flavours. On the algorithmic side, we propose an approximate counting procedure, valid in principle for a large class of graphs. On a more theoretical side, we study the typical number of long circuits in random graph ensembles, reproducing rigorously known results and stating new conjectures.

The objective of this collaborative textbook is to present the state of the art on games on graphs, which is part of a larger research topic called game theory. Games on graphs is the field concerned with games whose rules and evolution are represented by a graph.

This paper will contribute to a practical problem, Urban Traffic. We will investigate those features, try to simplify the complexity and formulize this dynamic system. These contents mainly contain how to analyze a decision problem with combinatorial method and graph theory algorithms; how to optimize our strategy to gain a feasible solution through employing other principles of Computer Science.

What is a complex network? How do we characterize complex networks? Which systems can be studied from a network approach? In this text, we motivate the use of complex networks to study and understand a broad panoply of systems, ranging from physics and biology to economy and sociology. Using basic tools from statistical physics, we will characterize the main types of networks found in nature. Moreover, the most recent trends in network research will be briefly discussed.

The paper presents a course on Combinatorial Algorithms that is based on the drafts of the author that he used while teaching the course in the Department of Informatics and Applied Mathematics of Yerevan State University, Armenia from February 2007 to June 2007.

According to Paul Erd\H{o}s [Some notes on Tur\'an's mathematical work, J. Approx. Theory 29 (1980), page 4] it was Paul Tur\'an who "created the area of extremal problems in graph theory". However, without a doubt, Paul Erd\H{o}s popularized extremal combinatorics, by his many contributions to the field, his numerous questions and conjectures, and his influence on discrete mathematicians in Hungary and all over the world. In fact, most of the early contributions in this fiel...

One or more searchers must capture an invisible evader hiding in the nodes of a graph. We study this graph search problem; we emphasize that we study the capture of a node-located evader, which has received less attention than edge search. We show that in general graphs the problem of node search is easier than that of edge search (however node search is NP-complete, just like edge search). We concentrate on the internal monotone connected (IMC) node search of trees and show ...

The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by J. K\"{o}rner in 1973. Although the notion of graph entropy has its roots in information theory, it was proved to be closely related to some classical and frequently studied graph theoretic concepts. For example, it provides an equivalent def...