A reduction method to find spanning Eulerian subgraphs

We ask, When does a graph G have a subgraph Γ such that the vertices of odd degree in Γ form a specified set S ? V(G), such that G - E(Γ) is connected? If such a subgraph can be found for a suitable choice of S, then this can be applied to problems such as finding a spanning eulerian subgraph of G. We provide a general method, with applications.     

A note on the monotonicity of mixed Ramsey numbers

For two graphs, G and H, an edge coloring of a complete graph is (G,H)-good if there is no monochromatic subgraph isomorphic to G and no rainbow subgraph isomorphic to H in this coloring. The set of numbers of colors used by (G,H)-good colorings of K_n is called a mixed Ramsey spectrum. This note addresses a fundamental question of whether the spectrum is an interval. It is shown that the answer is “yes” if G is not a star and H does not contain a pendant edge.     

Paired-Domination Subdivision Numbers of Graphs

A paired-dominating set of a graph G = (V, E) with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number sd _γpr (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. In this paper we establish upper bounds on the paired-domination subdivision number and pose some problems and conjectures.     

Orientation distance graphs

For two nonisomorphic orientations D and D′ of a graph G, the orientation distance d_o(D,D′) between D and D′ is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D′. The orientation distance graph 𝒟_o(G) of G has the set 𝒪(G) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D′ of 𝒟₀(G) are adjacent if and only if d_o(D,D′) = 1. For a nonempty subset S of 𝒪(G), the orientation distance graph 𝒟₀(S) of S is the induced subgraph 〈S〉 of 𝒟_o(G). A graph H is an orientation distance graph if there exists a graph G and a set S⊆ 𝒪(G) such that 𝒟_o(S) is isomorphic to H. In this case, H is said to be an orientation distance graph with respect to G. This paper deals primarily with orientation distance graphs with respect to paths. For every integer n ≥ 4, it is shown that 𝒟_o(P_n) is Hamiltonian if and only if n is even. Also, the orientation distance graph of a path of odd order is bipartite. Furthermore, every tree is an orientation distance graph with respect to some path, as is every cycle, and for n ≥ 3 the clique number of 𝒟_o(P_n) is 2 if n is odd and is 3 otherwise. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 230–241, 2001     

Randomly Orthogonal (g,f)-factorizations in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valued functions defined on V(G) such that 2k − 2 ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges. In this paper it is proved that every (mg + m − 1,mf − m + 1)-graph G has (g,f)-factorizations randomly k-orthogonal to H and shown that the result is best possible.     

Global cycle properties in graphs with large minimum clustering coefficient

Let 𝒫 be a graph property. A graph G is said to be locally 𝒫 (closed locally 𝒫) if the subgraph induced by the open neighbourhood (closed neighbourhood, respectively) of every vertex in G has property 𝒫. The clustering coefficient of a vertex is the proportion of pairs of its neighbours that are themselves neighbours. The minimum clustering coefficient of G is the smallest clustering coefficient among all vertices of G. Let H be a subgraph of a graph G and let S ? V (H). We say that H is a strongly induced subgraph of G with attachment set S, if H is an induced subgraph of G and the vertices of V (H) ? S are not incident with edges that are not in H. A graph G is fully cycle extendable if every vertex of G lies in a triangle and for every nonhamiltonian cycle C of G, there is a cycle of length |V (C)|?+?1 that contains the vertices of C. A complete characterization, of those locally connected graphs with minimum clustering coefficient 1/2 and maximum degree at most 6 that are fully cycle extendable, is given in terms of forbidden strongly induced subgraphs (with specified attachment sets). Moreover, it is shown that all locally connected graphs with Δ?≤?6 and sufficiently large minimum clustering coefficient are weakly pancylic, thereby proving Ryj´ǎcek’s conjecture for this class of graphs.     

On the number of subgraphs of prescribed type of graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For a graphH=〈V(H),E(H)〉 and forS ⊂V(H) defineN(S)={x ∈V(H):xy ∈E(H) for somey ∈S}. Define alsoδ(H)= max {|S| − |N(S)|:S ⊂V(H)},γ(H)=1/2(|V(H)|+δ(H)). For two graphsG, H letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also forl>0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We investigate the asymptotic behaviour ofN(l, H) for fixedH asl tends to infinity. The main results are:Theorem A. For every graph H there are positive constants c ₁, c₂ such that {fx116-1}. Theorem B. If δ(H)=0then {fx116-2},where |AutH|is the number of automorphisms of H. (It turns out thatδ(H)=0 iffH has a spanning subgraph which is a disjoint union of cycles and isolated edges.) This paper forms part of an M.Sc. Thesis written by the author under the supervision of Prof. M. A. Perles from the Hebrew University of Jerusalem.     

Simple exceptional groups of Lie type are determined by their character degrees

Let G be a finite group. Denote by Irr(G) the set of all irreducible complex characters of G. Let cd(G)={c(1)  |  c ? Irr(G)}{{\rm cd}(G)=\{\chi(1)\;|\;\chi\in {\rm Irr}(G)\}} be the set of all irreducible complex character degrees of G forgetting multiplicities, and let X₁(G) be the set of all irreducible complex character degrees of G counting multiplicities. Let H be any non-abelian simple exceptional group of Lie type. In this paper, we will show that if S is a non-abelian simple group and cd(S) í cd(H){{\rm cd}(S)\subseteq {\rm cd}(H)} then S must be isomorphic to H. As a consequence, we show that if G is a finite group with X₁(G) í X₁(H){{\rm X}_1(G)\subseteq {\rm X}_1(H)} then G is isomorphic to H. In particular, this implies that the simple exceptional groups of Lie type are uniquely determined by the structure of their complex group algebras.     

Closed Separator Sets

A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G. A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G. A graph H with is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán. Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree.     

Maximal sets of hamilton cycles in complete multipartite graphs

A set S of edge‐disjoint hamilton cycles in a graph G is said to be maximal if the edges in the hamilton cycles in S induce a subgraph H of G such that G ? E(H) contains no hamilton cycles. In this context, the spectrum S(G) of a graph G is the set of integers m such that G contains a maximal set of m edge‐disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs and for all complete bipartite graphs. In this paper, we extend these results to the complete multipartite graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 49–66, 2003     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

Set domination in graphs

Let G = (V, E) be a connected graph. A set D ? V is a set-dominating set (sd-set) if for every set T ? V ? D, there exists a nonempty set S ? D such that the subgraph 〈S ∪ T〉 induced by S ∪ T is connected. The set-domination number γ_s(G) of G is the minimum cardinality of a sd-set. In this paper we develop properties of this new parameter and relate it to some other known domination parameters.     

Subgraphs and the Laplacian spectrum of a graph

Let G be a graph and H a subgraph of G. In this paper, a set of pairwise independent subgraphs that are all isomorphic copies of H is called an H-matching. Denoting by ν(H,G) the cardinality of a maximum H-matching in G, we investigate some relations between ν(H,G) and the Laplacian spectrum of G.     

On Units of Group Algebras of 2-Groups of Maximal Class

Abstract

We determine the number of elements of order two in the group of normalized units V(𝔽₂ G) of the group algebra 𝔽₂ G of a 2-group of maximal class over the field 𝔽₂ of two elements. As a consequence for the 2-groups G and H of maximal class we have that V(𝔽₂ G) and V(𝔽₂ H) are isomorphic if and only if G and H are isomorphic.     

A Generalization of Orthogonal Factorizations in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valuated functions defined on V(G) such that g(x) ≤f(x) for all x∈V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤d _H (x) ≤f(x) for all x∈V(G). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let = {F ₁, F ₂, ..., F _m } be a factorization of G and H be a subgraph of G with mr edges. If F _i , 1 ≤i≤m, has exactly r edges in common with H, then is said to be r-orthogonal to H. In this paper it is proved that every (mg + kr, mf−kr)-graph, where m, k and r are positive integers with k < m and g≥r, contains a subgraph R such that R has a (g, f)-factorization which is r-orthogonal to a given subgraph H with kr edges. This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China     

A polynomial-time algorithm for the paired-domination problem on permutation graphs

A set S of vertices in a graph H=(V,E) with no isolated vertices is a paired-dominating set of H if every vertex of H is adjacent to at least one vertex in S and if the subgraph induced by S contains a perfect matching. Let G be a permutation graph and π be its corresponding permutation. In this paper we present an O(mn) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges.     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Alternating and Sporadic Simple Groups are Determined by Their Character Degrees

Let G be a finite group. Denote by Irr(G) the set of all irreducible complex characters of G. Let cd(G) be the set of all irreducible complex character degrees of G forgetting multiplicities, that is, cd(G) = {χ(1) : χ ∈ Irr(G)} and let cd ^*(G) be the set of all irreducible complex character degrees of G counting multiplicities. Let H be an alternating group of degree at least 5, a sporadic simple group or the Tits group. In this paper, we will show that if G is a non-abelian simple group and cd(G) í cd(H)cd(G)\subseteq cd(H) then G must be isomorphic to H. As a consequence, we show that if G is a finite group with cd^*(G) í cd^*(H)cd^*(G)\subseteq cd^*(H) then G is isomorphic to H. This gives a positive answer to Question 11.8 (a) in (Unsolved problems in group theory: the Kourovka notebook, 16th edn) for alternating groups, sporadic simple groups or the Tits group.     

Reconstructing the number of copies of a valency-labeled finite graph in an infinite graph

Suppose that G, H are infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such that G - ξ ? H - Ψ(ξ) for every ξ ～ V(G). Let J be a finite graph and /(π) be a cardinal number for each π ? V(J). Suppose also that either /(π) is infinite for every π ? V(J) or J has a connected subgraph C such that /(π) is finite for every π ? V(C) and every vertex in V(J)/V(C) is adjacent to a vertex of C. Let (J, I, G) be the set of those subgraphs of G that are isomorphic to J under isomorphisms that map each vertex π of J to a vertex whose valency in G is /(π). We prove that the sets (J, I, G), m(J, I, H) have the same cardinality and include equal numbers of induced subgraphs of G, H respectively.     

Clique Vertex Magic Cover of a Graph

Let G admit an H-edge covering and f : V èE ? {1,2,?,n+e}{f : V \cup E \to \{1,2,\ldots,n+e\}} be a bijective mapping for G then f is called H-edge magic total labeling of G if there is a positive integer constant m(f) such that each subgraph H _i , i = 1, . . . , r of G is isomorphic to H and f(H_i)=f(H)=S_{v ? V(Hi)}f(v)+S_{e ? E(Hi)} f(e)=m(f){f(H_i)=f(H)=\Sigma_{v \in V(H_i)}f(v)+\Sigma_{e \in E(H_i)} f(e)=m(f)}. In this paper we define a subgraph-vertex magic cover of a graph and give some construction of some families of graphs that admit this property. We show the construction of some C _n - vertex magic covered and clique magic covered graphs.