Academic literature on the topic 'THEORY OF SIGNED GRAPHS'

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.

Dans cette thèse, nous etudions deux principaux problèmes de la théorie des graphes: problème d’homomorphisme des graphes planaires (signés) et problème de cycle hamiltonien.Comme une extension du théorème des quatre couleurs, il est conjecturé([80], [41]) que chaque graphe signé cohérent planaire de déséquilibré-maille d+1(d&gt;1) admet un homomorphisme à cube projective signé SPC(d) de dimension d. La question suivant étalés naturelle:Est-ce que SPC(d) une borne optimale de déséquilibré-maille d+1 pour tous les graphes signés cohérente planaire de déséquilibré-maille d+1?Au Chapitre 2, nous prouvons que: si (B,Ω) est un graphe signé cohérente dedéséquilibré-maille d qui borne la classe des graphes signés cohérents planaires de déséquilibré-maille d+1, puis |B| ≥2^{d−1}. Notre résultat montre que si la conjecture ci-dessus est vérifiée, alors le SPC(d) est une borne optimale à la fois en terme du nombre des sommets et du nombre de arêtes.Lorsque d=2k, le problème est équivalent aux problème des graphes:est-ce que PC(2k) une borne optimale de impair-maille 2k+1 pour P_{2k+1} (tous les graphes planaires de impair-maille au moins 2k+1)? Notez que les graphes K_4-mineur libres sont les graphes planaires, est PC(2k) aussi une borne optimale de impair-maille 2k+1 pour tous les graphes K_4-mineur libres de impair-maille 2k+1? La réponse est négative, dans[6], est donné une famille de graphes d’ordre O(k^2) que borne les graphes K_4-mineur libres de impair-maille 2k+1. Est-ce que la borne optimale? Au Chapitre 3, nous prouvons que: si B est un graphe de impair-maille 2k+1 qui borne tous les graphes K_4-mineur libres de impair-maille 2k+1, alors |B|≥(k+1)(k+2)/2. La conjonction de nos résultat et le résultat dans [6] montre que l’ordre O(k^2) est optimal. En outre, si PC(2k) borne P_{2k+1}, PC(2k) borne également P_{2r+1}(r&gt;k).Cependant, dans ce cas, nous croyons qu’un sous-graphe propre de P(2k) serait suffisant à borner P_{2r+1}, alors quel est le sous-graphe optimal de PC2k) qui borne P_{2r+1}? Le premier cas non résolu est k=3 et r= 5. Dans ce cas, Naserasr [81] a conjecturé que le graphe Coxeter borne P_{11}. Au Chapitre 4, nous vérifions cette conjecture pour P_{17}.Au Chapitres 5, 6, nous étudions les problèmes du cycle hamiltonien. Dirac amontré en 1952 que chaque graphe d’ordre n est hamiltonien si tout sommet a un degré au moins n/2. Depuis, de nombreux résultats généralisant le théorème de Dirac sur les degré ont été obtenus. Une approche consiste à construire un cycle hamiltonien à partir d'un ensemble de sommets en contrôlant leur position sur le cycle. Dans cette thèse, nous considérons deux conjectures connexes. La première est la conjecture d'Enomoto: si G est un graphe d’ordre n≥3 et δ(G)≥n/2+1, pour toute paire de sommets x,y dans G, il y a un cycle hamiltonien C de G tel que dist_C(x,y)=n/2.Notez que l’ ́etat de degre de la conjecture de Enomoto est forte. Motivé par cette conjecture, il a prouvé, dans [32], qu’une paire de sommets peut être posé des distances pas plus de n/6 sur un cycle hamiltonien. Dans [33], les cas δ(G)≥(n+k)/2 sont considérés, il a prouvé qu’une paire de sommets à une distance entre 2 à k peut être posé sur un cycle hamiltonien. En outre, Faudree et Li ont proposé une conjecture plus générale: si G est un graphe d’ordre n≥3 et δ(G)≥n/2+1, pour toute paire de sommets x,y dans G et tout entier 2≤k≤n/2, il existe un cycle hamiltonien C de G tel que dist_C(x,y)=k. Utilisant de Regularity Lemma et Blow-up Lemma, au chapitre 5, nous donnons une preuve de la conjeture d'Enomoto conjecture pour les graphes suffisamment grand, et dans le chapitre 6, nous donnons une preuve de la conjecture de Faudree et Li pour les graphe suffisamment grand<br>In this thesis, we study two main problems in graph theory: homomorphism problem of planar (signed) graphs and Hamiltonian cycle problem.As an extension of the Four-Color Theorem, it is conjectured ([80],[41]) that every planar consistent signed graph of unbalanced-girth d+1(d&gt;1) admits a homomorphism to signed projective cube SPC(d) of dimension d. It is naturally asked that:Is SPC(d) an optimal bound of unbalanced-girth d+1 for all planar consistent signed graphs of unbalanced-girth d+1?In Chapter 2, we prove that: if (B,Ω) is a consistent signed graph of unbalanced-girth d which bounds the class of consistent signed planar graphs of unbalanced-girth d, then |B|≥2^{d-1}. Furthermore,if no subgraph of (B,Ω) bounds the same class, δ(B)≥d, and therefore,|E(B)|≥d·2^{d-2}.Our result shows that if the conjecture above holds, then the SPC(d) is an optimal bound both in terms of number of vertices and number of edges.When d=2k, the problem is equivalent to the homomorphisms of graphs: isPC(2k) an optimal bound of odd-girth 2k+1 for P_{2k+1}(the class of all planar graphs of odd-girth at least 2k+1)? Note that K_4-minor free graphs are planar graphs, is PC(2k) also an optimal bound of odd-girth 2k+1 for all K_4-minor free graphs of odd-girth 2k+1 ? The answer is negative, in [6], a family of graphs of order O(k^2) bounding the K_4-minor free graphs of odd-girth 2k+1 were given. Is this an optimal bound? In Chapter 3, we prove that: if B is a graph of odd-girth 2k+1 which bounds all the K_4-minor free graphs of odd-girth 2k+1,then |B|≥(k+1)(k+2)/2. Our result together with the result in [6] shows that order O(k^2) is optimal.Furthermore, if PC(2k) bounds P_{2k+1},then PC(2k) also bounds P_{2r+1}(r&gt;k). However, in this case we believe that a proper subgraph of PC(2k) would suffice to bound P_{2r+1}, then what’s the optimal subgraph of PC(2k) that bounds P_{2r+1}? The first case of this problem which is not studied is k=3 and r=5. For this case, Naserasr [81] conjectured that the Coxeter graph bounds P_{11} . Supporting this conjecture, in Chapter 4, we prove that the Coxeter graph bounds P_{17}.In Chapter 5,6, we study the Hamiltonian cycle problems. Dirac showed in 1952that every graph of order n is Hamiltonian if any vertex is of degree at least n/2. This result started a new approach to develop sufficient conditions on degrees for a graph to be Hamiltonian. Many results have been obtained in generalization of Dirac’s theorem. In the results to strengthen Dirac’s theorem, there is an interesting research area: to control the placement of a set of vertices on a Hamiltonian cycle such that thesevertices have some certain distances among them on the Hamiltonian cycle.In this thesis, we consider two related conjectures, one is given by Enomoto: if G is a graph of order n≥3, and δ(G)≥n/2+1, then for any pair of vertices x, y in G, there is a Hamiltonian cycle C of G such that dist_C(x, y)=n/2. Motivated by this conjecture, it is proved,in [32],that a pair of vertices are located at distances no more than n/6 on a Hamiltonian cycle. In [33], the cases δ(G) ≥(n+k)/2 are considered, it is proved that a pair of vertices can be located at any given distance from 2 to k on a Hamiltonian cycle. Moreover, Faudree and Li proposed a more general conjecture: if G is a graph of order n≥3, and δ(G)≥n/2+1, then for any pair of vertices x, y in G andany integer 2≤k≤n/2, there is a Hamiltonian cycle C of G such that dist_C(x, y) = k. Using Regularity Lemma and Blow-up Lemma, in Chapter 5, we give a proof ofEnomoto’s conjecture for graphs of sufficiently large order, and in Chapter 6, we give a proof of Faudree and Li’s conjecture for graphs of sufficiently large order

Graph Signal Processing (GSP), as the field concerned with the extension of classical signal processing concepts to the graph domain, is still at the beginning on the path toward providing a generalized theory of signal processing. As such, this thesis aspires to conceive the theory of sparse representations on graphs by traversing the cornerstones of wavelet and sampling theory on graphs. Beginning with the novel topic of graph spline wavelet theory, we introduce families of spline and e-spline wavelets, and associated filterbanks on circulant graphs, which lever- age an inherent vanishing moment property of circulant graph Laplacian matrices (and their parameterized generalizations), for the reproduction and annihilation of (exponen- tial) polynomial signals. Further, these families are shown to provide a stepping stone to generalized graph wavelet designs with adaptive (annihilation) properties. Circulant graphs, which serve as building blocks, facilitate intuitively equivalent signal processing concepts and operations, such that insights can be leveraged for and extended to more complex scenarios, including arbitrary undirected graphs, time-varying graphs, as well as associated signals with space- and time-variant properties, all the while retaining the focus on inducing sparse representations. Further, we shift from sparsity-inducing to sparsity-leveraging theory and present a novel sampling and graph coarsening framework for (wavelet-)sparse graph signals, inspired by Finite Rate of Innovation (FRI) theory and directly building upon (graph) spline wavelet theory. At its core, the introduced Graph-FRI-framework states that any K-sparse signal residing on the vertices of a circulant graph can be sampled and perfectly reconstructed from its dimensionality-reduced graph spectral representation of minimum size 2K, while the structure of an associated coarsened graph is simultaneously inferred. Extensions to arbitrary graphs can be enforced via suitable approximation schemes. Eventually, gained insights are unified in a graph-based image approximation framework which further leverages graph partitioning and re-labelling techniques for a maximally sparse graph wavelet representation.

Le spectre du Laplacien sans signe a fait l'objet de beaucoup d'attention dans la communauté scientifique ces dernières années. La principale raison est l'intuition, basée sur une étude des petits graphes et sur des propriétés valides pour des graphes de toutes tailles, que plus de graphes sont déterminés par le spectre de cette matrice que par celui de la matrice d'adjacence et du Laplacien. Les travaux présentés dans cette thèse ont apporté des éléments nouveaux sur les informations contenues dans le spectre cette matrice. D'une part, on y présente des relations entre les invariants de structure et une valeur propre du Laplacien sans signe. D'autre part, on présente des familles de graphes extrêmes pour deux de ses valeurs propres, avec et sans contraintes additionnelles sur la forme de graphe. Il se trouve que ceux-ci sont très similaires à ceux obtenus dans les mêmes conditions avec les valeurs propres de la matrice d'adjacence. Cela aboutit à la définition de familles de graphes pour lesquelles, le spectre du Laplacien sans signe ou une de ses valeurs propres, le nombre de sommets et un invariant de structure suffisent à déterminer le graphe. Ces résultats, par leur similitude avec ceux de la littérature viennent confirmer l'idée que le Laplacien sans signe détermine probablement aussi bien les graphes que la matrice d'adjacence.

Clustering is the process in which data is differentiated, classified according to some criteria. As a result of partitioning process, data is grouped into clusters for specific purpose. In a social network, clustering of people is one of the most popular problems. Therefore, we mainly concentrated on finding an efficient algorithm for this problem. In our study, data is made up of two types of entities (e.g., people, groups vs. political issues, religious beliefs) and distinct from most previous works, signed weighted bipartite graphs are used to model relations among them. For the partitioning criterion, we use the strength of the opinions between the entities. Our main intention is to partition the data into k-clusters so that entities within clusters represent strong relationship. One such example from a political domain is the opinion of people on issues. Using the signed weights on the edges, these bipartite graphs can be partitioned into two or more clusters. In political domain, a cluster represents strong relationship among a group of people and a group of issues. After partitioning, each cluster in the result set contains like-minded people and advocated issues. Our work introduces a general mechanism for k-way partitioning of signed bipartite graphs. One of the great advantages of our thesis is that it does not require any preliminary information about the structure of the input dataset. The idea has been illustrated on real and randomly generated data and promising results have been shown.