A characterization of self-complementary graphs of order 8
A characterization of semi bound graphs.
A characterization of singular graphs.
A characterization of the decay number of a connected graph
A characterization of the interval function of a connected graph
A characterization of the interval function of a (finite or infinite) connected graph
By the interval function of a finite connected graph we mean the interval function in the sense of H. M. Mulder. This function is very important for studying properties of a finite connected graph which depend on the distance between vertices. The interval function of a finite connected graph was characterized by the present author. The interval function of an infinite connected graph can be defined similarly to that of a finite one. In the present paper we give a characterization of the interval...
A characterization of the set of all shortest paths in a connected graph
Let be a (finite undirected) connected graph (with no loop or multiple edge). The set of all shortest paths in is defined as the set of all paths , then the lenght of does not exceed the length of . While the definition of is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of : a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...
A Characterization of Trees for a New Lower Bound on the K-Independence Number
Let k be a positive integer and G = (V,E) a graph of order n. A subset S of V is a k-independent set of G if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. The maximum cardinality of a k-independent set of G is the k-independence number βk(G). In this paper, we show that for every graph [xxx], where χ(G), s(G) and Lv are the chromatic number, the number of supports vertices and the number of leaves neighbors of v, in the graph G, respectively. Moreover,...
A characterization of (γₜ,γ₂)-trees
Let γₜ(G) and γ₂(G) be the total domination number and the 2-domination number of a graph G, respectively. It has been shown that: γₜ(T) ≤ γ₂(T) for any tree T. In this paper, we provide a constructive characterization of those trees with equal total domination number and 2-domination number.
A class of 4-pseudomanifolds similar to the lense spaces.
A class of Cayley graphs induced by right solvable ward groupoids
A class of inequalities relating degrees of adjacent nodes to the average degree in edge-weighted uniform hypergraphs.
A class of tight circulant tournaments
A tournament is said to be tight whenever every 3-colouring of its vertices using the 3 colours, leaves at least one cyclic triangle all whose vertices have different colours. In this paper, we extend the class of known tight circulant tournaments.
A class of weakly perfect graphs
A graph is called weakly perfect if its chromatic number equals its clique number. In this note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.
A classification for maximal nonhamiltonian Burkard-Hammer graphs
A graph G = (V,E) is called a split graph if there exists a partition V = I∪K such that the subgraphs G[I] and G[K] of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for a split graph G with |I| < |K| to be hamiltonian. We will call a split graph G with |I| < |K| satisfying this condition a Burkard-Hammer graph. Further, a split graph G is called a maximal nonhamiltonian split graph if G is nonhamiltonian but G+uv is...
A classification of Ramanujan unitary Cayley graphs.
A classification of separable Rosenthal compacta and its applications [Book]
A classification of tetravalent one-regular graphs of order 3p²
A graph is one-regular if its automorphism group acts regularly on the set of its arcs. In this paper, tetravalent one-regular graphs of order 3p², where p is a prime, are classified.
A clone-theoretic formulation of the Erdos-Faber-Lovász conjecture
The Erdős-Faber-Lovász conjecture states that if a graph G is the union of n cliques of size n no two of which share more than one vertex, then χ(G) = n. We provide a formulation of this conjecture in terms of maximal partial clones of partial operations on a set.
A co-ideal based identity-summand graph of a commutative semiring
Let be a strong co-ideal of a commutative semiring with identity. Let be a graph with the set of vertices for some , where two distinct vertices and are adjacent if and only if . We look at the diameter and girth of this graph. Also we discuss when is bipartite. Moreover, studies are done on the planarity, clique, and chromatic number of this graph. Examples illustrating the results are presented.