The coordinate representation of a graph and n-universal graph of radius 1

Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space Eⁿ. Cube vertices have integer coordinates. The coordinate matrix, A(G)={v_nk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements v_nk≠v_pk. We show that Bp(G)=cub(G) for some graphs, and Bp(G)n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3ⁿ⁻² vertices that contains as an induced subgraph a copy of any graph on n vertices.     

Codes with girth 8 Tanner graph representation

Since short cycles are (empirically) detrimental to message passing, determining the girth of a given code is of interest in coding theory. Halford et al. studied codes which do not have a 4-cycle-free Tanner graph representation. It is natural to then ask which codes must have girth 8. In this paper, a new necessary condition is derived for codes to have girth 8. Halford et al. made statements about the girth of high rate well known codes but the girth of lower rate codes remain open. In this work, we investigate girth of low rate Reed–Muller, BCH and Reed–Solomon codes.     

Existence, uniqueness and graph representation of weighted minimal hypersurfaces

By means of a weight matrix, we introduce the class of weighted minimal hypersurfaces which yield a natural generalisation of minimal surfaces. Generalising a classical result of Radó, we prove existence, uniqueness and graph representation for weighted minimal hypersurfaces in \mathbbRⁿ⁺¹{\mathbb{R}^{n+1}} with prescribed boundary manifold.     

Knowledge management in semantic social networks

An object-oriented model of semantic social networks is proposed and formally analyzed. Methods for project, role, and team management based on the semantic model are defined and implemented in $\mathfrak{n}\mathfrak{i}\mathbf{K}\mathfrak{l}\mathfrak{a}\mathfrak{s}$ , a semantic wiki language based on frame logic developed by the author. The new approach to semantic social networks allows dynamic change of social network semantics and the establishment of the well known fishnet organization in a social network. In the end possible applications to knowledge management are presented.     

The product representation of a locally dependent random graph

Directed graphs with random black and white colourings of edges such that the colours of edges from different vertices are mutually independent are called locally dependent random graphs. Two random graphs are equivalent if they cannot be distinguished from percolation processes on them if only the vertices are seen. A necessary and sufficient condition is given for when a locally dependent random graph is equivalent to a product random graph; that is one in which the edges can be grouped in such a way that within each group the colours of the edges are equivalent and between groups they are independent. As an application the random graph corresponding to a spatial general epidemic model is considered.     

On the path representation of networks

A compact data structure for networks is obtained by storing arcs of paths sequentially. This structure allows forward and backward access from a node to its neighbors.     

Communicability graph and community structures in complex networks

We use the concept of the network communicability [E. Estrada, N. Hatano, Communicability in complex networks, Phys. Rev. E 77 (2008) 036111] to define communities in a complex network. The communities are defined as the cliques of a “communicability graph”, which has the same set of nodes as the complex network and links determined by the communicability function. Then, the problem of finding the network communities is transformed to an all-clique problem of the communicability graph. We discuss the efficiency of this algorithm of community detection. In addition, we extend here the concept of the communicability to account for the strength of the interactions between the nodes by using the concept of inverse temperature of the network. Finally, we develop an algorithm to manage the different degrees of overlapping between the communities in a complex network. We then analyze the USA airport network, for which we successfully detect two big communities of the eastern airports and of the western/central airports as well as two bridging central communities. In striking contrast, a well-known algorithm groups all but two of the continental airports into one community.     

The computational complexity of graph problems with succinct multigraph representation

The complexity of graph problems is investigated when the graphs are presented asvertex multiplicity graphs. In this presentation an independent set of vertices which are connected in the same way with the remaining vertices of the graph can be described by giving only one vertex and the size of the independent set in binary. Using this succinct graph presentation one can expect that the complexity of graph problems can blow up exponentially. In fact, it is shown that the RNC-problems UNARY NETWORK FLOW and PERFECT MATCHING becomeP-complete, that the NP-complete problems CHLIQUE, MAXIMUM INDEPENDENT SET and CHROMATIC NUMBER remain NP-complete and that aP-complete version of the CIRCUIT VALUE problem becomes PSPACE-complete.Supported in part by DFG Grant WA 594/1-1.     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

Magnetic Eigenmaps for the visualization of directed networks

We propose a framework for the visualization of directed networks relying on the eigenfunctions of the magnetic Laplacian, called here Magnetic Eigenmaps. The magnetic Laplacian is a complex deformation of the well-known combinatorial Laplacian. Features such as density of links and directionality patterns are revealed by plotting the phases of the first magnetic eigenvectors. An interpretation of the magnetic eigenvectors is given in connection with the angular synchronization problem. Illustrations of our method are given for both artificial and real networks.     

Feynman graph representation of the perturbation series for general functional measures

A representation of the perturbation series of a general functional measure is given in terms of generalized Feynman graphs and rules. The graphical calculus is applied to certain functional measures of Lévy type. A graphical notion of Wick ordering is introduced and is compared with orthogonal decompositions of the Wiener-Itô-Segal type. It is also shown that the linked cluster theorem for Feynman graphs extends to generalized Feynman graphs. We perturbatively prove existence of the thermodynamic limit for the free energy density and the moment functions. The results are applied to the gas of charged microscopic or mesoscopic particles—neutral in average—in d=2 dimensions generating a static field φ with quadratic energy density giving rise to a pair interaction. The pressure function for this system is calculated up to fourth order. We also discuss the subtraction of logarithmically divergent self-energy terms for a gas of only one particle type by a local counterterm of first order.     

Directed graph representation of half-rate additive codes over GF(4)

We show that (n, 2 ⁿ ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 ⁿ ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.     

Some transport and diffusion processes on networks and their graph realizability

In this paper we consider systems of transport and diffusion problems on one-dimensional domains coupled through transmission type boundary conditions at the endpoints and determine what types of such problems can be identified with respective problems on metric graphs. For the transport problem the answer is provided by a reformulation of a graph theoretic result characterizing line digraphs of a digraph, whereas in the case of diffusion the answer is provided by an algebraic characterization of matrices which are adjacency matrices of line graphs, which complements known results from graph theory and is particularly suitable for this application.     

On a class of packet-switching networks on an infinite graph

A class of open queueing networks with packet switching is discussed. The configuration graph of the network may be finite or infinite. The external messages are divided into standard pieces (packets) each of which is transmitted as a single message. The messages are addressed, as a rule, to nearest neighbours and thereby the network may be treated as a small perturbation of the collection of isolated servers. The switching rule adopted admits overtaking: packets which appeared later may reach the delivery node earlier. The transmission of a message is completed when its last packet reaches the destination node. The main result of this paper is that the network possesses a unique stationary working regime. Weak dependence properties of this regime are established as well as the continuity with respect to the parameters of the external message flows.