A binary clutter is cycling if its packing and covering linear program have integral optimal solutions for all Eulerian edge capacities. We prove that the clutter of odd st- walks of a signed graph is cycling if and only if it does not contain as a minor the clutter of odd circuits of K5 nor the clutter of lines of the Fano matroid. Corollaries of this result include, of many, the characterization for weakly bipartite signed graphs, packing two- commodity paths, packing T-joins with small |T|, a new result on covering odd circuits of a signed graph, as well as a new result on covering odd circuits and odd T-joins of a signed graft.

A graph in which every edge is labeled positive or negative is called a signed graph. We determine the number of ways to sign the edges of the McGee graph with exactly two negative edges up to switching isomorphism. We characterize signed graphs that are both sign-symmetric and have a frustration index of 1. We prove some results about which signed graphs on complete multipartite graphs have frustration indices 2 and 3. In the final part, we derive the relationship between the frustration index and the number of parts in a sign-symmetric signed graph on complete multipartite graphs.

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>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>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. / 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>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>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.

This thesis targets at providing an algebraic method to indicate network behaviors. Furthermore, for a signed-average consensus problem of the system behaviors, event-triggering signed-average algorithms are designed to reduce the communication overheads. In Chapter 1, the background is introduced, and the problem is formulated. In Chapter 2, notations and basics of graph theory are presented. It is known that the terminal value of the system state is determined by the initial state, left eigenvector and right eigenvector associated with zero eigenvalue of the Laplacian matrix. Since there is no mathematical expression of right eigenvector, in Chapter 3, mathematical expression of right eigenvector is given. In Chapter 4, algebraic trait for structurally balanced property of a node is proposed. In Chapter 5, a method for characterization of collective behaviors under directed signed networks is developed. In Chapter 6, dynamic event-triggering signed-average algorithms are proposed and proved for the purpose of relieving the communication burden between agents. Chapter 7 summarizes the thesis and gives future directions.

In this dissertation, we investigate various aspects of signed graphs, with a particular focus on signings and sign-symmetric signed graphs. We begin by examining the complete graph on six vertices with one edge deleted ($K_6$\textbackslash e) and explore the different ways of signing this graph up to switching isomorphism. We determine the frustration index (number) of these signings and investigate the existence of sign-symmetric signed graphs. We then extend our study to the $K_6$\textbackslash 2e graph and the McGee graph with exactly two negative edges. We investigate the distinct ways of signing these graphs up to switching isomorphism and demonstrate the absence of sign-symmetric signed graphs in some cases. We then introduce and study the signed graph class $\mathcal{S}$, which includes all sign-symmetric signed graphs, we prove several theorems and lemmas as well as discuss the class of tangled sign-symmetric signed graphs. Also, we study the graph class $\mathcal{G}$, consisting of graphs with at least one sign-symmetric signed graph, prove additional theorems and lemmas, and determine certain families within $\mathcal{G}$. Our results have practical applications in various fields such as social psychology and computer science.