Uniquely Total Colorable Graphs

Uniquely vertex colorable graphs and uniquely edge colorable graphs have been studied extensively by different authors. The literature on the similar problem for total coloring is void. In this paper we study this concept and, among other results, we prove that if a graph G ≠ K ₂ is uniquely total colorable, then χ″(G) = Δ + 1. Our results support the following conjecture: empty graphs, paths, and cycles of order 3k, k a natural number, are the only uniquely total colorable graphs.     

Constructing Uniquely Realizable Graphs

In the Graph Realization Problem (GRP), one is given a graph  $G$ , a set of non-negative edge-weights, and an integer  $d$ . The goal is to find, if possible, a realization of  $G$ in the Euclidian space $\mathbb R ^d$ , such that the distance between any two vertices is the assigned edge weight. The problem has many applications in mathematics and computer science, but is NP-hard when the dimension  $d$ is fixed. Characterizing tractable instances of GRP is a classical problem, first studied by Menger in 1931. We construct two new infinite families of GRP instances which can be solved in polynomial time. Both constructions are based on the blow-up of fixed small graphs with large expanders. Our main tool is the Connelly’s condition in Rigidity Theory, combined with an explicit construction and algebraic calculations of the rigidity (stress) matrix. As an application of our results, we describe a general framework to construct uniquely k-colorable graphs. These graphs have the extra property of being uniquely vector k-colorable. We give a deterministic explicit construction of such a family using Cayley expander graphs.     

关于几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m＜n)使对每个l∈{3,4,…,n} -{m},G恰有一个长为l的圈且不含长为m的圈,则称G是几乎唯一泛圈图,用(?)k表示具有n k条边和恰有1/2(k 1)(k 2)个圈的简单H图的集合,用(?)_k~*表示具有n k条边恰有2~k k个圈的简单外可平面H图的集合,本文确定了(?)_k和(?)_k~*中所有几乎唯一泛圈图,并证明这些图都是简单MCD图,本文还构造了50个含有同胚于K_4的子图的几乎唯一泛圈图,并提出了若干问题和猜想。     

Uniquely Cycle‐Saturated Graphs

Given a graph F, a graph G is uniquely F‐saturated if F is not a subgraph of G and adding any edge of the complement to G completes exactly one copy of F. In this article, we study uniquely ‐saturated graphs. We prove the following: (1) a graph is uniquely C₅‐saturated if and only if it is a friendship graph. (2) There are no uniquely C₆‐saturated graphs or uniquely C₇‐saturated graphs. (3) For , there are only finitely many uniquely ‐saturated graphs (we conjecture that in fact there are none). Additionally, our results show that there are finitely many k‐friendship graphs (as defined by Kotzig) for .     

A Note on Uniquely lntersectable Graphs

The following conjecture of Alter and Wang is proven. Consider the intersection graph G_n,m,n?2m, determined by the family of all m-element subsets of an n-element set. Then any realization of G_n,m as an intersection graph by a family of sets satisfies |∪_iA_i|?n; and if |∪_iA_i|=n, then F must be the family of all m-element subsets of ∪_iA_i.     

关于唯一r—泛圈图的两个结果

本文证明了对r≥5，不存在r-UPC[2]图和对r≥3,不存在r-UPC[Ct^2]图，这里t是图中桥数，Ct^2是t条桥中任取2条的组合数。     

Uniquely Edge-3-Colorable Graphs and Snarks

 A cubic graph G is uniquely edge-3-colorable if G has precisely one 1-factorization. It is proved in this paper, if a uniquely edge-3-colorable, cubic graph G is cyclically 4-edge-connected, but not cyclically 5-edge-connected, then G must contain a snark as a minor. This is an approach to a conjecture that every triangle free uniquely edge-3-colorable cubic graph must have the Petersen graph as a minor. Fiorini and Wilson (1976) conjectured that every uniquely edge-3-colorable planar cubic graph must have a triangle. It is proved in this paper that every counterexample to this conjecture is cyclically 5-edge-connected and that in a minimal counterexample to the conjecture, every cyclic 5-edge-cut is trivial (an edge-cut T of G is cyclic if no component of G\T is acyclic and a cyclic edge-cut T is trivial if one component of G\T is a circuit of length |T|). Received: July 14, 1997 Revised: June 11, 1998     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

Uniquely Hamiltonian Graphs of Minimum Degree 4

We construct an infinite family of uniquely hamiltonian graphs of minimum degree 4, maximum degree 14, and of arbitrarily high maximum degree.     

一类几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m相似文献   

On Unicyclic Graphs with Uniquely Restricted Maximum Matchings

A graph is called unicyclic if it owns only one cycle. A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. Clearly, μ _r (G) ≤ μ(G), where μ _r (G) denotes the size of a maximum uniquely restricted matching, while μ(G) equals the matching number of G. In this paper we study unicyclic bipartite graphs enjoying μ _r (G) = μ(G). In particular, we characterize unicyclic bipartite graphs having only uniquely restricted maximum matchings. Finally, we present some polynomial time algorithms recognizing unicyclic bipartite graphs with (only) uniquely restricted maximum matchings.     

A Construction of Uniquely C4-free colourable Graphs

Abstract

An F-free colouring of a graph G is a partition {V₁,V₂,…,V_n} of the vertex set V(G) of G such that F is not an induced subgraph of G[V_i] for each i. A graph is uniquely F-free colourable if any two .F-free colourings induce the same partition of V(G). We give a constructive proof that uniquely C₄-free colourable graphs exist.     

The Zero-Divisor Graphs Which Are Uniquely Determined By Neighborhoods

A nonempty simple connected graph G is called a uniquely determined graph, if distinct vertices of G have distinct neighborhoods. We prove that if R is a commutative ring, then Γ(R) is uniquely determined if and only if either R is a Boolean ring or T(R) is a local ring with x² = 0 for any x ∈ Z(R), where T(R) is the total quotient ring of R. We determine all the corresponding rings with characteristic p for any finite complete graph, and in particular, give all the corresponding rings of K_n if n + 1 = p^q for some primes p, q. Finally, we show that a graph G with more than two vertices has a unique corresponding zero-divisor semigroup if G is a zero-divisor graph of some Boolean ring.     

P4-Reducible Graphs—Class of Uniquely Tree-Representable Graphs

We introduce and characterize a new class of graphs which has a unique tree representation, and which strictly contains the well-known class of cographs. We define three graph operations and show that all the graphs in our class can be constructed from single-vertex graphs by a finite sequence of these operations. Finally, we show that a number of computational problems, including the four classical optimization problems, can be solved efficiently for this new class of graphs.     

θ*r,s,t-图与唯一2-列表染色图的特征化

如果一个图G存在一个k-列表安排使得G具有一个唯一列表染色,则称 G是唯一列表可染色图,简称UkLC图．我们称图G具有M(k)性质当且仅当G不 是UkLC图．本文在借鉴θr,s,t-图概念的基础上引入θr,s,t-图的定义,并证明:除了 r=s=t=2以外,θr,s,t-图都是U2LC图．利用如上结果我们给出M．Mahdian and E．S．Mahmoodian对U2LC图所作特征化的一个简单证明．     

Uniquely pairable graphs

The concept of a k-pairable graph was introduced by Z. Chen [On k-pairable graphs, Discrete Mathematics 287 (2004), 11-15] as an extension of hypercubes and graphs with an antipodal isomorphism. In the present paper we generalize further this concept of a k-pairable graph to the concept of a semi-pairable graph. We prove that a graph is semi-pairable if and only if its prime factor decomposition contains a semi-pairable prime factor or some repeated prime factors. We also introduce a special class of k-pairable graphs which are called uniquely k-pairable graphs. We show that a graph is uniquely pairable if and only if its prime factor decomposition has at least one pairable prime factor, each prime factor is either uniquely pairable or not semi-pairable, and all prime factors which are not semi-pairable are pairwise non-isomorphic. As a corollary we give a characterization of uniquely pairable Cartesian product graphs.     

Uniquely Covered Groups

In this paper, we investigate finite groups which have exactly one irredundant covering by proper subgroups.2000 Mathematics Subject Classification: 20E07     

Uniquely Complemented Posets

We study complementation in bounded posets. It is known and easy to see that every complemented distributive poset is uniquely complemented. The converse statement is not valid, even for lattices. In the present paper we provide conditions that force a uniquely complemented poset to be distributive. For atomistic resp. atomic posets as well as for posets satisfying the descending chain condition we find sufficient conditions in the form of so-called LU-identities. It turns out that for finite posets these conditions are necessary and sufficient.